2317 - 删边游戏

一个无向图,其中某些点是重要的。两人在该图上进行游戏,轮流操作。每次操作是指将某条边删去,该边必须与某个重要点连通,谁无法操作则输掉了游戏。 Your Task 判断先手是否有必胜策略。

Input

第一行T表示数据组数 对于每组数据,第一行n m分别表示点数、边数,点从1到n编号 第二行p表示重要点的个数 第三行p个数表示重要点的编号 接下来m行每行三个数i j k表示点i与点j之间有k条边

Output

对于每组数据,在一行中输出答案,若先手必胜输出1否则输出0

Examples

Input

2

3 2

1

1

1 2 1

2 3 1

2 1

1

1

1 2 2

Output

1

0
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题