放石子

【题目描述】

YJC最近写了一篇关于游戏的论文。CJY看他那么喜欢游戏，决定出一道题考考他。CJY给出了一种两个人玩的游戏。 定义游戏规则如下：给一张$n$个点，$m$条边的有向无环图，每条边有颜色$c$，在图上放了$q$颗石子，每颗石子在一个点上。每次操作时选择一个有出边且点上有石子的点$x$，从点上取走一颗石子，然后选择一个颜色集合$S$，对于每条满足颜色$e∈S$的出边$i$，在边$i$的终点上放上一颗石子。双方轮流操作，不能操作者负。CJY问YJC是先手获胜还是后手获胜。YJC很轻松地解决了这个问题。 CJY把数据规模放大了。YJC遇到了困难，于是他来向你求助。

【输入】

第$1$行包含两个整数$n$和$m$，表示图的点数和边数。 第$2$到$m+1$行每行包含三个整数$s$,$t$和$c$，表示一条边的起点、终点和颜色。 接下来一行包含一个整数$q$，表示石子数量。 接下来一行包含$q$个整数，表示每颗石子所在的点。

【输出】

输出一个整数，如果先手必胜则输出$1$，否则输出$0$。

【输入样例】

2 1
2 1 1
1
2

【输出样例】

1

【提示】

【数据规模与约定】 实际测试时使用捆绑测试，一个测试点包含多个分测试点。 对于20%的数据，$n≤5,m≤10,q≤20$。 对于30%的数据，$n≤20,m≤100, q≤100$。 对于100%的数据，$n≤200,m≤5000,q≤10000,c≤5000$。