스핑크스의 수수께끼

위대한 스핑크스가 당신에게 수수께끼를 냈습니다. 정점이 $N$개인 그래프가 주어집니다. 정점은 0부터 $N - 1$까지 번호가 매겨져 있습니다. 간선은 $M$개이며 0부터 $M - 1$까지 번호가 매겨져 있습니다. 각 간선은 양방향이고 서로 다른 두 정점을 잇습니다. 간선 $j$는 정점 $X[j]$와 $Y[j]$를 잇습니다. 같은 두 정점을 잇는 간선은 최대 하나입니다. 두 정점이 간선으로 이어져 있으면 인접하다고 합니다. 정점들의 수열 $v_0, v_1, \dots, v_k$ ($k \ge 0$)에서 연속한 두 정점 $v_l$과 $v_{l+1}$이 모두 인접하면 이 수열을 경로라고 합니다. 이 경로는 $v_0$과 $v_k$를 잇습니다. 주어진 그래프에서는 모든 정점 쌍이 어떤 경로로 연결되어 있습니다.

색은 $N + 1$개이며 0부터 $N$까지 번호가 매겨져 있습니다. 색 $N$은 특별하며 스핑크스의 색이라고 부릅니다. 정점 $i$ ($0 \le i < N$)의 색은 $C[i]$입니다. 여러 정점이 같은 색을 가질 수 있고, 어떤 색은 어떤 정점에도 배정되지 않을 수 있습니다. 스핑크스의 색을 가진 정점은 없으므로 $0 \le C[i] < N$입니다.

경로 $v_0, v_1, \dots, v_k$ ($k \ge 0$)의 모든 정점 색이 같으면 이 경로를 단색 경로라고 합니다. 즉 $0 \le l < k$인 모든 $l$에 대해 $C[v_l] = C[v_{l+1}]$입니다. 두 정점 $p$와 $q$ ($0 \le p < N$, $0 \le q < N$)는 단색 경로로 연결되어 있을 때, 그리고 그때에만 같은 단색 컴포넌트에 속합니다.

정점과 간선은 알고 있지만 정점의 색은 모릅니다. 재색칠 실험을 수행해 정점의 색을 알아내십시오.

재색칠 실험에서는 임의의 개수의 정점을 다시 칠할 수 있습니다. 먼저 크기가 $N$인 배열 $E$를 고릅니다. 각 $E[i]$는 $-1$ 이상 $N$ 이하입니다. 정점 $i$의 색 $S[i]$는 $E[i] = -1$이면 $C[i]$이고, 그렇지 않으면 $E[i]$입니다. 그러면 스핑크스가 색 $S$를 적용한 그래프의 단색 컴포넌트 개수를 알려줍니다. 새 색칠은 이 실험에만 적용되며, 실험이 끝나면 모든 정점은 원래 색으로 돌아갑니다. 재색칠에 스핑크스의 색도 쓸 수 있습니다.

최대 $2\,750$번의 재색칠 실험으로 모든 정점의 색을 알아내십시오. 인접한 정점의 각 쌍이 같은 색인지 정확히 판단하면 부분 점수를 받을 수도 있습니다.

• $2 \le N \le 250$
• $N - 1 \le M \le \frac{N \cdot (N-1)}{2}$
• 각 $j$ ($0 \le j < M$)에 대해 $0 \le X[j] < Y[j] < N$
• 각 $j$, $k$ ($0 \le j < k < M$)에 대해 $X[j] \ne X[k]$ 또는 $Y[j] \ne Y[k]$
• 모든 정점 쌍은 어떤 경로로 연결되어 있다.
• 각 $i$ ($0 \le i < N$)에 대해 $0 \le C[i] < N$