石子移动

题目描述

你正在玩一种游戏，定义游戏规则如下：给一张 $n$ 个点， $m$ 条边的有向无环图，每条边都有颜色 $c$ ，在图上放了 $q$ 颗石子，每颗石子在一个点上。

每次操作时选择一个有出边且点上有石子的点 $x$ ，从点上取走一颗石子，然后选择一个颜色集合 $S$ ，对于每条 $x$ 满足颜色 $e \in S$ 的出边 $i$ （可以没有），在边 $i$ 的终点上放上一颗石子。双方轮流操作，不能操作者负。

你想知道是先手获胜还是后手获胜。

第一行包含两个整数 $n$ 和 $m$ ，表示图的点数和边数。

第 $2$ 到 $m+1$ 行每行包含三个整数 $s$ ， $t$ 和 $c$ ，表示一条边的起点、终点和颜色。

接下来一行包含一个整数 $q$ ，表示石子数量。

接下来一行包含 $q$ 个整数，表示每颗石子所在的点。

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

对于 $100\%$ 的数据， $1 < n < 200$ ， $1 < m < 5000$ ， $1 \leq q \leq 10000$ ， $1 < c < 5000$ 。

本题采用子任务捆绑测试。对于每个子任务，你只有通过了这个子任务的所有数据，才能获得这个子任务的分数。

见stonemove2.in

见stonemove2.out