Toy Train 玩具火车

本题改编自 IOI 2017 Toy Train 玩具火车

这个村庄有 $n$ 户人家，编号从 $0$ 到 $n-1$， $m$ 条道路，每个道路有一个起点和终点，乐乐侠只能从道路的起点出发到终点，不能反着走，否则魔法会减少。乐乐侠准备从某一个起点出发向 $n$ 户人家膜拜后离开(只要累计膜拜过$n$ 户人家即可，不需要看是否相同还是不相同)。但是，有些人家的人很善良，在乐乐侠膜拜完之后会给予一些关心慰问甚至是资金的帮助，因此乐乐侠膜拜完后会满怀激动，此时他会决定重新膜拜 $n$ 户人家之后才会离开村庄。 可惜他的膜拜计划走漏了风声，被库拉知道了，库拉观察了乐乐侠所要膜拜的村庄的结构后发现：乐乐侠无论从哪户人家开始出发，最终一定会落入一个环，即在某一些人家中按照顺序重复的膜拜，直至膜完。于是库拉有了让乐乐侠一直在村庄膜拜下去直至老去的阴谋。他在村庄的各户人家布置下了一些魔法阵，其魔法阵分为两种： $\cdot$ 第一种魔法阵的效果是：当乐乐侠首次经过那个布置了这种魔法阵的人家，魔法阵会记录他的离开的道路，一旦再次经过那户人家时，魔法阵会使他走第一次走过的道路； $\cdot$ 第二种魔法阵的效果是：可以在布置这种魔法阵的人家控制乐乐侠走固定的一条道路， 即当乐乐侠经过布置了第二种魔法阵的人家时，只会固定不变走库拉设定的一条道路。 若乐乐侠一直没有停止膜拜下去，则库拉的就会得逞，否则就没有得逞。作为聪明的你，肯定不想要乐乐侠落入库拉的魔爪中。因此，在给出上述的条件下，请你判断，乐乐侠从那些人家出发后，无论他怎么走，库拉的计划都可以得逞。

第一行为两个正整数 $n$ 和 $m$，分别描述村庄中人家的数量以及道路的数量。 接下来一行，有 $n$ 个正整数 $r_i$，若 $r_i=0$，则说明在编号为 $i-1$ 的编号的人家布下的是第一种魔法阵；若 $r_i=1$，说明在编号为 $i-1$ 个的人家布下的是第二种魔法阵。 接下来一行，有 $n$ 个正整数 $p_i$，若 $p_i=0$，则说明编号为 $i-1$ 的编号的人家不是善良的人家；若 $p_i=1$，则说明编号为 $i-1$ 个的人家是善良的人家。 接下来 $m$ 行，每行两个正整数 $u$ 和 $v$，表示一条道路的起点和终点分别为编号是 $u$ 和 $v$ 的的人家。

输出 $n$ 行，在第 $i$ 行，若乐乐侠从第 $i-1$ 户人家出发后，无论他怎么走，库拉的计划都可以得逞则输出 `Yes`，否则输出 `No`。

2 4
0 1
1 0
0 0
0 1
1 0
1 1

Yes
Yes

15 26
0 1 0 0 1 1 0 0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0 0 0 1 0 1 0 0
0 10
12 6
3 7
12 14
4 10
3 14
8 12
12 12
5 5
11 11
4 5
4 14
14 11
12 11
6 8
3 3
13 3
1 5
3 10
13 8
9 2
5 10
7 4
1 4
10 5
2 4

Yes
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
No
No
No
No

在 样例 1 中，有 $n=2$ 户人家，其中 0 号人家为善良的人家，布下的是第一种魔法阵； 1号人家布下的是第二种魔法阵。 这里有 4 条道路 $(0,0)$、$(0,1)$、$(1,0)$ 和 $(1,1)$，其中 $(i, j)$ 描述一条以编号为 $i$ 的人家为起点，编号为 $j$ 的人家为终点的道路。 样例 1 中描述的村庄的地图如下图所示：  考虑乐乐侠从 0 号人家出发的情况，如果乐乐侠走起点终点都为 0 的道路，他每一次在 0号店后又会要再走 2 个点，而魔法阵会限制乐乐侠走起点终点都为 0 的道路，因此因此乐乐侠回到 0 号人家后又会要再走 2 个点的想法，而此想法在实现前，乐乐侠又会回到 0 号人家。库拉的阴谋会得逞；若走通向 1 号点的道路，库拉的膜法阵可以控制乐乐侠走通向 0 号点得道路，因此乐乐侠回到 0 号人家后又会要再走 2 个点的想法，而此想法在实现前，乐乐侠又会回到 0 号人家，库拉的阴谋也会得逞。因此在从 0 号人家出发的情况下库拉的阴谋会得逞。 若乐乐侠从 1 号人家出发，库拉的魔法阵可以控制乐乐侠走通向 0 号点得道路，后面情况如上述所述，因此在从 1 号人家出发的情况下库拉的阴谋也会得逞。 ## 子任务 在所有的测试点中，保证 $1 \le n \le 5 \times 10^3$，$n \le m \le 2 \times 10^4$。每个人家至少有一条以它为起点的道路，且所有的道路不会相同。 本题共 25 个测试点，每个测试点 4 分，各个测试点的数据范围如下表所示：  ## 题解 https://www.luogu.org/discuss/show?postid=52662