열쇠

건축가 티모시가 새로운 탈출 게임을 설계했다. 이 게임에는 0번부터 $n - 1$번까지 번호가 붙은 $n$개의 방이 있다. 처음에 각 방에는 열쇠가 정확히 하나씩 들어 있다. 각 열쇠에는 0 이상 $n - 1$ 이하의 정수인 종류가 있다. $i$번 방의 열쇠 종류는 $r[i]$이다. 여러 방에 같은 종류의 열쇠가 있을 수 있으므로 값 $r[i]$가 서로 다르다고 보장되지는 않는다.

양방향 통로가 $m$개 있으며 번호는 0번부터 $m - 1$번까지이다. 통로 $j$($0 \le j \le m - 1$)는 서로 다른 두 방 $u[j]$와 $v[j]$를 잇는다. 같은 두 방을 여러 통로로 이어도 된다.

플레이어는 혼자서 열쇠를 모으고 통로를 따라 방 사이를 이동한다. 플레이어가 $u[j]$에서 $v[j]$로, 또는 $v[j]$에서 $u[j]$로 이동하면 통로 $j$를 지나는 것이다. 통로 $j$는 종류 $c[j]$인 열쇠를 이미 모은 뒤에만 지날 수 있다. 플레이어는 모은 열쇠를 버리지 않는다.

플레이어는 어떤 방 $x$에 있을 때 다음 두 가지 행동을 할 수 있다.

• 방 $x$의 열쇠(종류 $r[x]$)를 모은다. 이미 모은 열쇠라면 다시 모을 필요는 없다.
• $u[j] = x$ 또는 $v[j] = x$인 통로 $j$를 지난다. 이때 종류 $c[j]$인 열쇠를 이미 모아 두었어야 한다.

플레이어는 열쇠가 없는 상태로 방 $s$에서 출발한다. 방 $s$에서 출발한 플레이어가 위의 행동을 순서대로 수행해 방 $t$에 도달할 수 있으면, 방 $t$는 방 $s$에서 도달 가능하다.

각 방 $i$($0 \le i \le n - 1$)에 대해 $p[i]$를 방 $i$에서 도달 가능한 방의 개수라고 하자. 티모시는 $0 \le i \le n - 1$ 범위에서 $p[i]$가 최솟값을 갖는 인덱스 $i$들의 집합을 알고 싶어 한다.

• $2 \le n \le 300\,000$
• $1 \le m \le 300\,000$
• 모든 $0 \le i \le n - 1$에 대해 $0 \le r[i] \le n - 1$
• 모든 $0 \le j \le m - 1$에 대해 $0 \le u[j], v[j] \le n - 1$이고 $u[j] \ne v[j]$
• 모든 $0 \le j \le m - 1$에 대해 $0 \le c[j] \le n - 1$