여기 어디야

where

[0]

出题人: k_san

문제

정점 수 $N$ , 간선 수 $M$ 인 무방향 단순 그래프가 주어진다. 그래프의 정점은 $1$ 번부터 $N$ 번까지 번호가 매겨져 있다. 각 정점은 $1$ 이상 $N$ 이하 중 하나의 색깔로 색칠되어 있으며 각 정점에는 플레이어가 정확히 한 명씩 존재한다.

提交需要登录。

각 플레이어는 처음에 자신이 위치한 정점의 번호를 알지 못하지만 다음의 정보를 알고 있다.

게임은 턴제로 진행되며 모든 플레이어는 완벽한 논리적 추론 능력을 갖추고 있다. 매 턴마다 다음 과정이 동시다발적으로 일어난다.

남아있는 각 플레이어는 현재까지 주어진 정보들을 바탕으로 자신이 위치한 정점의 번호를 추론한다. 만약 자신이 위치한 정점의 번호를 확실하게 알아냈다면 해당 턴에 탈출을 선언한다.
탈출을 선언한 모든 플레이어는 동시에 그래프에서 제거되며 이들이 위치했던 정점과 연결된 모든 간선도 함께 삭제된다.
간선이 삭제됨에 따라 자신이 위치한 정점에 남은 간선의 수가 몇 개로 변했는지도 알게 된다. 이 정보들은 다음 턴의 추론에 사용된다.

각 정점에 있는 플레이어가 몇 번째 턴에 탈출하는지를 구하시오. 만약 어떤 플레이어가 아무리 턴이 지나도 끝내 자신의 정점 번호를 확실하게 알아낼 수 없다면 해당 플레이어의 탈출 턴은 -1로 출력한다.

첫 번째 줄에 정점 수 $N$ 과 간선 수 $M$ 이 공백으로 구분되어 주어진다. $(1 \le N, M \le 3 \times 10^5)$

두 번째 줄에 각 정점의 색깔 $C_1, C_2, \dots, C_N$ 이 공백으로 구분되어 주어진다.

세 번째 줄부터 $M$ 개의 줄에 걸쳐 간선의 양 끝 정점 $U_i, V_i$ 가 공백으로 구분되어 주어진다. $(1 \leq U_{i}, V_{i} \leq N; U_{i} \neq_{}$

첫 번째 줄에 $1$ 번 정점부터 $N$ 번 정점에 있는 각 플레이어가 탈출하는 턴 혹은 -1을 공백으로 구분하여 출력한다.

#	分数	数据范围
1	100	-

样例输入

样例输出

1 2 -1 -1

(1 \le C_i \le N)

(1 \leq C_{i} \leq N)

V

i

)

(1 \le U_i, V_i \le N; U_i \neq V_i)

(1 \leq U_{i}, V_{i} \leq N; U_{i} \neq = V_{i})

[0]