Keys

Timothy the architect has designed a new escape 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]$. Several rooms may hold keys of the same type, so the values $r[i]$ are not necessarily distinct.

There are $m$ bidirectional connectors numbered from $0$ to $m - 1$. Connector $j$ ($0 \le j \le m - 1$) joins two different rooms $u[j]$ and $v[j]$. A pair of rooms can be joined by more than one connector.

A single player collects keys and moves between rooms through the connectors. The player traverses connector $j$ when they move from $u[j]$ to $v[j]$ or from $v[j]$ to $u[j]$. The player can traverse connector $j$ only after collecting a key of type $c[j]$. The player never discards a key.

The player is in some room $x$ and can perform two kinds of actions:

• Collect the key in room $x$, whose type is $r[x]$, unless it has already been collected.
• Traverse connector $j$, where $u[j] = x$ or $v[j] = x$, if the player has already collected a key of type $c[j]$.

The player starts in room $s$ carrying no keys. Room $t$ is reachable from room $s$ if the player starting in room $s$ can perform some sequence of these actions and end up in room $t$.

For each room $i$ ($0 \le i \le n - 1$), let $p[i]$ be the number of rooms reachable from room $i$. Timothy wants to know the set of indices $i$ that attain the minimum value of $p[i]$ over $0 \le i \le n - 1$.

• $2 \le n \le 300\,000$
• $1 \le m \le 300\,000$
• $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$