P6560 [SBCOI2020] 时光的流逝
题目背景
时间一分一秒的过着，伴随着雪一同消融在了这个冬天，
或许，要是时光能停留在这一刻，该有多好啊。
......
“这是...我在这个小镇的最后一个冬天了吧。”
“嗯，你可不能这辈子都呆在这个小镇吧。外面的世界很大呢，很大很大...”
“唔...外面的世界...突然有点期待呢！”
“总有一天，你会走得很远很远。以后你可不要忘记这个小镇那。”
“不会的，至少...这里曾经是我最快乐的一段回忆呢！你也一定不要忘记我呀。”
“你看，这雪花。传说，每当世界上有一份思念，便会化成一片雪花在这里飘落。”
“那...以后你可一定要找到我的那片雪花啊......”
“嗯，不如我们一起在这个冬天创造最后一段回忆吧。”
“好呀，我们玩个游戏吧......”
题目描述
这个游戏是在一个有向图（不保证无环）上进行的。每轮游戏开始前，她们先在图上选定一个起点和一个终点，并在起点处放上一枚棋子。
然后两人轮流移动棋子，每次可以将棋子按照有向图的方向移动至相邻的点。
如果谁先将棋子移动至终点，那么谁就胜利了。同样，如果谁无法移动了，那么谁就失败了。
两人轮流操作，请问，他们是否有必胜策略呢？
答案为一个整数 `0` 或 `1` 或 `-1`，其中 `1` 表示（先手）有必胜策略，`-1` 表示后手有必胜策略，`0` 表示两人均无必胜策略。
输入格式
无
输出格式
无
说明/提示
#### 样例解释 $#1$
为描述题意，假设两人为 A（先手）和 B
如图，A 先走，走到 $2$，B 走到 $3$，接下去 A 可以选择走到 $4$ 或 $6$，若走到 $4$，接下去 B 可以走到终点，故不可取。若选择走到 $6$，那么 B 只能走到 $7$，A 可以走到终点。所以 A 有必胜策略。
#### 样例解释 $#2$
如图，起点为 $1$，终点为 $5$ 时， A 和 B 会沿着 $1-2-3-1$ 的顺序轮流走。因为如果谁先走到 $4$，那么下一个人就可以走到终点。故谁都没有必胜策略。
起点为 $4$，终点为 $3$ 时，A 先走到 $5$，B 无路可走，故 B 失败。
#### 数据范围
对于 $10\%$ 的数据，保证图是一条链。
对于 $50\%$ 的数据，$1\leq n\leq 10^3$，$1\leq m\leq 2\times10^3$，$1\leq q\leq 10$。
对于 $70\%$ 的数据，$1\leq n\leq 10^5$，$1\leq m\leq 2\times10^5$，$1\leq q\leq 10$。
对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq m\leq 5\times10^5$，$1\leq q\leq 500$。