Background

Due to technical limitations, please do not use C++14 (GCC 9) to submit this problem.

This is an interactive problem. You only need to implement the function required in the code.

Your code does not need to include any extra header files, and you do not need to implement the main function.

Problem Description

Architect Timothy designed a new escape-room game.

In this game, there are $n$ rooms, numbered from $0$ to $n - 1$. At the beginning, each room contains exactly one key. Each key has a type, and the type is an integer in the range $0$ to $n - 1$. The key in room $i$ has type $r[i]$. Note that multiple rooms may contain keys of the same type, so the values $r[i]$ are not necessarily pairwise distinct.

The game also has $m$ undirected corridors, numbered from $0$ to $m - 1$. Corridor $j$ connects two different rooms $u[j]$ and $v[j]$. There may be multiple corridors between the same pair of rooms.

Players need to collect keys and move between rooms through corridors. When a player uses corridor $j$ to move from room $u[j]$ to room $v[j]$, or from room $v[j]$ to room $u[j]$, we say the player passes through corridor $j$. A player can pass through corridor $j$ only if the player has collected a key of type $c[j]$.

At any time, when the player is in some room $x$, the player can perform the following two operations:

• Collect the key in room $x$, whose type is $r[x]$ (unless a key of that type has already been collected).
• Pass through corridor $j$, where $u[j] = x$ or $v[j] = x$, and the player has already obtained a key of type $c[j]$.

Note that any key the player has collected can be used forever and is never discarded.

Initially, the player starts the game in some room $s$, with no keys. If the player starts from room $s$ and can reach room $t$ by performing a sequence of the two operations described above, then room $t$ is said to be reachable from room $s$.

For each room $i ~ ( 0 \le i \le n − 1)$, let $p[i]$ be the number of rooms that can be reached starting from room $i$. Timothy wants to know the set of indices $i$ for which $p[i]$ is minimal.

Input Format

You need to implement the following function:

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

• $r$: a sequence of length $n$. For each $i ~ ( 0 \leq i \leq n − 1)$, the key type in room $i$ is $r[i]$.
• $u, v$: two sequences of length $m$. For each $j ~ ( 0 \leq j \leq m − 1)$, corridor $j$ connects rooms $u[j]$ and $v[j]$.
• $c$: a sequence of length $m$. For each $j ~ ( 0 \leq j \leq m − 1)$, passing through corridor $j$ requires a key of type $c[j]$.

Output Format

• The function should return a sequence $a$ of length $n$. For $i$ in $0 \leq i \leq n − 1$, if $p[i] \leq p[j] ~ (0 \leq j \leq n − 1)$, then $a[i] = 1$; otherwise, $a[i] = 0$.

4 5
0 1 1 2
0 1 0
0 2 0
1 2 1
1 3 0
3 1 2

0 1 1 0

7 10
0 1 1 2 2 1 2
0 1 0
0 2 0
1 2 1
1 3 0
2 3 0
3 4 1
3 5 2
4 5 0
4 6 2
5 6 1

0 1 1 0 1 0 1

3 1
0 0 0
0 1 0

0 0 1

Hint

Sample Explanation

For 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 from room $0$, they can perform the following sequence of operations:

Therefore, room $3$ is reachable starting from room $0$. Similarly, we can construct operation sequences showing that all $4$ rooms are reachable from room $0$, so $p[0] = 4$. The table below shows the set of reachable rooms starting from each room:

The minimum value of $p[i]$ among all rooms is $2$, which is achieved at $i = 1$ or $i = 2$. Therefore, the return value of this function call is $[0, 1, 1, 0]$.

For Example $2$: the minimum value of $p[i]$ among all rooms is $2$, which is achieved at $i \in \{1, 2, 4, 6\}$. Therefore, the return value of this function call is $[0, 1, 1, 0, 1, 0, 1]$.

For Example $3$: the minimum value of $p[i]$ among all rooms is $1$, which is achieved at $i = 2$. Therefore, the return value of this function call is $[0, 0, 1]$.

Constraints

• $2 \leq n \leq 3 \times 10 ^ 5$.
• $1 \leq m \leq 3 \times 10 ^ 5$.
• $0 \leq r[i] \leq n - 1$ (for all $0 \leq i \leq n - 1$).
• $0 \leq u[j], v[j] \leq n - 1$ and $u[j] \neq v[j]$ (for all $0 \leq j \leq m - 1$).
• $0 \leq c[j] \leq n - 1$ (for all $0 \leq j \leq m - 1$).

Subtasks

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

Sample Grader

The sample grader reads the input in the following format:

• Line $1$: $n ~ m$.
• Line $2$: $r[0] ~ r[1] ~ \cdots ~ r[n − 1]$.
• Line $3 + j$ $( 0 \leq j \leq m − 1)$: $u[j] ~ v[j] ~ c[j]$.

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

• Line $1$: $s[0] ~ s[1] \cdots ~ s[n − 1]$.

Translated by ChatGPT 5