题目描述

Arezou 和她的兄弟 Borzou 是双胞胎。他们收到的生日礼物是一套好玩的玩具火车。他们用它建了一个有 $n$ 个车站和 $m$ 段单向轨道的铁路系统。这些车站的编号是从 $0$ 到 $n - 1$。每段轨道都始于某一车站，然后终于同一车站或其他车站。每个车站至少会有一段轨道以它为起点。

其中有些车站是充电车站。无论何时，如果火车抵达某个充电车站，它都会被充到满电。满电火车拥有足够的动力连续地驶过 $n$ 段轨道，但是如果不再充电的话，在即将进入第 $n + 1$ 段轨道时它就会因电已用光而停车。

每个车站都有一个轨道开关，可以扳向任一以该车站为起点的轨道。火车从某个车站驶出时，驶向的正是该车站的开关所扳向的轨道。

这对双胞胎打算用他们的火车玩个游戏。他们已经分完了所有的车站：每个车站要么归 Arezou，要么归 Borzou。游戏里面只有一列火车。游戏开始时，这列火车停在车站 $s$，并且充满了电。为启动游戏，车站 $s$ 的拥有者把车站 $s$ 的开关扳向某个以 $s$ 为起点的轨道。随后他们启动火车，火车也就开始沿着轨道行驶。

无论何时，在火车首次进入某一车站时，该车站的拥有者都要扳定车站开关。开关一旦扳定，它就会保持状态不变直到游戏结束。因此，火车如果开到了一个曾经进过的车站，就会沿着与之前相同的轨道开出该车站。

由于车站数量是有限的，火车的行驶最终都会落入某个环路。环路是指一系列不同的车站 $c_0, c_1, \cdots , c_{k - 1}$，其中火车在离开车站 $c_i(0 \leq i < k - 1)$ 后驶上连向车站 $c_{i + 1}$ 的轨道，在离开车站 $c_{k - 1}$ 后驶上连向车站 $c_0$ 的轨道。一个环路可能只包括一个车站（此时 $k = 1$），即火车从车站 $c_0$ 驶出后又驶上了连向车站 $c_0$ 的轨道。

如果火车能够连续行驶跑完，Arezou 就赢了。否则火车最后会把电用光而停车，这样 Borzou 就赢了。换句话说，如果在车站 $c_0, c_1, \cdots , c_{k - 1}$ 中至少有一个充电车站，且使得火车能够不断地充电而沿着环路跑个没完，Arezou 赢。否则，它就会最终把电用光（有可能是在沿着环路跑好几圈后），Borzou 赢。

现在给你一个这样的铁路系统。Arezou 和 Borzou 将会玩 $n$ 轮游戏。其中在第 $s$ 轮游戏中 $(0 \leq s \leq n - 1)$，火车最初停在车站 $s$ 上。你的任务是，对每一轮游戏，判断是否无论 Borzou 怎么玩，Arezou 都必胜。

输入格式

你需要实现下面的函数：

int[] who_wins(int[] a, int[] r, int[] u, int[] v)

• $a$：长度为 $n$ 的数组。如果 Arezou 拥有车站 $i$，则 $a_i = 1$；否则 Borzou 拥有车站 $i$，且 $a_i=0$。
• $r$：长度为 $n$ 的数组。如果车站 $i$ 是充电车站，则 $r_i = 1$；否则 $r_i=0$。
• $u$ 和 $v$：长度为 $m$ 的数组。对于所有 $0 \leq i \leq m - 1$，存在某一单向轨道，其起点为 $u_i$，终点为 $v_i$。
• 该函数需要返回一个长度为 $n$ 的数组 $w$。对于每个 $0 \leq i \leq n - 1$，如果在火车最初停在车站 $i$ 的游戏中，不管 Borzou 怎么玩，Arezou 都能赢，则 $w_i$ 的值应为 $1$。否则 $w_i$ 的值应为 $0$。

数据范围与提示

限制条件：

• $1 \leq n \leq 5, 000$。
• $n \leq m \leq 20, 000$。
• 至少会有一个充电车站。
• 每个车站至少会有一段轨道以它为起点。
• 可能有某个轨道的起点和终点是相同的（即 $u_i = v_i$）。
• 所有轨道两两不同。也就是说，也就是说，不存在这样的两个下标 $i, j(0 \leq i < j \leq m - 1)$，使得 $u_i = u_j$ 且 $v_i = v_j$。
• 对于所有 $0 \leq i \leq m - 1$，都有 $0 \leq u_i, v_i \leq n - 1$。

子任务：

1. （5分）对于所有有向轨道，都有 $v = u$ 或者 $v = u + 1$。
2. （10分）$n \leq 15$。
3. （11分）Arezou 拥有所有车站。
4. （11分）Borzou 拥有所有车站。
5. （12分）充电车站的数量为 1。
6. （51分）没有任何的附加限制。

评分程序样例：

评分程序样例将会读入以下格式的数据：

• 第 $1$ 行：$n\ m$
• 第 $2$ 行：$a_0\ a_1\ \cdots\ a_{n - 1}$
• 第 $3$ 行：$r_0\ r_1\ \cdots\ r_{n - 1}$
• 第 $4 + i$ 行（对于所有 $0 \leq i \leq m - 1$）：$u_i\ v_i$

评分程序样例将会按照下述格式打印出 who_wins 的返回结果：

• 第 $1$ 行：$w_0\ w_1\ \cdots\ w_{n - 1}$