Timothy the architect has designed a new escape game. In this game, there are $n$ rooms numbered from $0$ to $n-1$. Initially, each room contains exactly one key. Each key has a type, which is an integer between $0$ and $n-1$, inclusive. The type of the key in room $i$ $(0\le i\le n-1)$ is $r[i]$. Note that multiple rooms may contain keys of the same type, i.e., the values $r[i]$ are not necessarily distinct.

There are also $m$ bidirectional connectors in the game, numbered from $0$ to $m-1$. Connector $j$ $(0\le j\le m-1)$ connects a pair of different rooms $u[j]$ and $v[j]$. A pair of rooms can be connected by multiple connectors.

The game is played by a single player who collects the keys and moves between the rooms by traversing the connectors. We say that the player traverses connector $j$ when they use this connector to move from room $u[j]$ to room $v[j]$, or vice versa. The player can only traverse connector $j$ if they have collected a key of type $c[j]$ before.

At any point during the game, the player is in some room $x$ and can perform two types of actions:

• collect the key in room $x$, whose type is $r[x]$ (unless they have collected it already),
• traverse a connector $j$, where either $u[j]=x$ or $v[j]=x$, if the player has collected a key of type $c[j]$ beforehand. Note that the player never discards a key they have collected.

The player starts the game in some room $s$ not carrying any keys. A room $t$ is reachable from a room $s$, if the player who starts the game in room $s$ can perform some sequence of actions described above, and reach room $t$.

For each room $i$ $(0\le i\le n-1)$, denote the number of rooms reachable from room $i$ as $p[i]$. Timothy would like to know the set of indices $i$ that attain the minimum value of $p[i]$ across $0\le i\le n-1$.

Implementation Details

You are to implement the following procedure:

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c)

• $r$: an array of length $n$. For each $i$ $(0\le i\le n-1)$, the key in room $i$ is of type $r[i]$.
• $u$, $v$: two arrays of length $m$. For each $j$ $(0\le j\le m-1)$, connector $j$ connects rooms $u[j]$ and $v[j]$.
• $c$: an array of length $m$. For each $j$ $(0\le j\le m-1)$, the type of key needed to traverse connector $j$ is $c[j]$.
• This procedure should return an array $a$ of length $n$. For each $0\le i\le n-1$, the value of $a[i]$ should be $1$ if for every $j$ such that $0\le j\le n-1$, $p[i]\le p[j]$. Otherwise, the value of $a[i]$ should be $0$.

Examples

Example 1

Consider the following call:

find_reachable({0, 1, 1, 2},
               {0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2})

If the player starts the game in room $0$, they can perform the following sequence of actions:

Current room	Action
$0$	Collect key of type $0$
$0$	Traverse connector $0$ to room $1$
$1$	Collect key of type $1$
$1$	Traverse connector $2$ to room $2$
$2$	Traverse connector $2$ to room $1$
$1$	Traverse connector $3$ to room $3$

Hence room $3$ is reachable from room $0$. Similarly, we can construct sequences showing that all rooms are reachable from room $0$, which implies $p[0]=4$. The table below shows the reachable rooms for all starting rooms:

Starting room $i$	Reachable rooms	$p[i]$
$0$	$[0,1,2,3]$	$4$
$1$	$[1,2]$	$2$
$2$	$[1,2]$	$2$
$3$	$[1,2,3]$	$3$

The smallest value of $p[i]$ across all rooms is $2$, and this is attained for $i=1$ or $i=2$. Therefore, this procedure should return $[0,1,1,0]$.

Example 2

find_reachable({0, 1, 1, 2, 2, 1, 2},
               {0, 0, 1, 1, 2, 3, 3, 4, 4, 5},
               {1, 2, 2, 3, 3, 4, 5, 5, 6, 6},
               {0, 0, 1, 0, 0, 1, 2, 0, 2, 1})

The table below shows the reachable rooms:

Starting room $i$	Reachable rooms	$p[i]$
$0$	$[0,1,2,3,4,5,6]$	$7$
$1$	$[1,2]$	$2$
$2$	$[1,2]$	$2$
$3$	$[3,4,5,6]$	$4$
$4$	$[4,6]$	$2$
$5$	$[3,4,5,6]$	$4$
$6$	$[4,6]$	$2$

The smallest value of $p[i]$ across all rooms is $2$, and this is attained for $i\in \{1,2,4,6\}$. Therefore, this procedure should return $[0,1,1,0,1,0,1]$.

Example 3

find_reachable({0, 0, 0}, {0}, {1}, {0})

The table below shows the reachable rooms:

Starting room $i$	Reachable rooms	$p[i]$
$0$	$[0,1]$	$2$
$1$	$[0,1]$	$2$
$2$	$[2]$	$1$

The smallest value of $p[i]$ across all rooms is $1$, and this is attained when $i=2$. Therefore, this procedure should return $[0,0,1]$.

Constraints

• $2\le n\le 300000$
• $1\le m\le 300000$
• $0\le r[i]\le n-1$ for all $0\le i\le n-1$
• $0\le u[j],v[j]\le n-1$ and $u[j]\ne v[j]$ for all $0\le j\le m-1$
• $0\le c[j]\le n-1$ for all $0\le j\le m-1$

Subtasks

1. ($9$ points) $c[j]=0$ for all $0\le j\le m-1$ and $n,m\le 200$
2. ($11$ points) $n,m\le 200$
3. ($17$ points) $n,m\le 2000$
4. ($30$ points) $c[j]\le 29$ (for all $0\le j\le m-1$) and $r[j]\le 29$ (for all $0\le i\le n-1$)
5. ($33$ points) No additional constraints.

Sample Grader

The sample grader reads the input in the following format:

• line $1$: $nm$
• line $2$: $r[0]r[1]\dots r[n-1]$
• line $3+j$ $(0\le j\le m-1)$: $u[j]v[j]c[j]$

The sample grader prints the return value of find_reachable in the following format:

• line $1$: $a[0]a[1]\dots a[n-1]$

Attachment Package

The sample grader and sample test cases are available here: keys.zip.