색칠

무방향 그래프 $G=(V,E)$가 주어진다. 함수 $c:V\to\mathbb{N}$은 모든 간선 $(u,v)\in E$에 대해 $c(u)\neq c(v)$이면 색칠(colouring)이라고 한다.

모든 정점 $v\in V$에 대해 $c(v)\in\{1,2,\ldots,k\}$이면 색칠 $c$를 아름다운(beautiful) 색칠이라고 한다. 즉 1부터 $k$까지의 색만 사용하는 색칠이 아름다운 색칠이다.

모든 정점 $v\in V$에 대해 $w\neq v$이고 $c(v)=c(w)$인 정점 $w\in V$가 존재하면 색칠 $c$를 똑똑한(smart) 색칠이라고 한다. 즉 사용된 모든 색이 최소 두 번 이상 쓰인 색칠이 똑똑한 색칠이다.

Byteasar는 자신의 그래프에 맞는 색칠을 찾고 있다. 그는 이미 아름다운 색칠 $c_b$를 찾았지만 너무 단순하고 야심이 부족해 보였다. 다른 때에는 똑똑한 색칠 $c_s$를 찾았지만, 얼마 지나지 않아 더는 쳐다볼 수 없었다.

Byteasar는 아름다우면서 동시에 똑똑한 색칠을 만날 희망을 잃었다. 그를 놀라게 하고, 그런 색칠을 찾아줄 수 있겠는가?

첫 줄에 세 정수 $n$, $m$, $k$가 주어진다 ($1\leq k \leq n \leq 200\,000$, $0 \leq m \leq 200\,000$). $k$는 아름다운 색칠에서 허용되는 가장 큰 색이고, $n$과 $m$은 각각 Byteasar 그래프의 정점 수와 간선 수이다. 정점은 1번부터 $n$번까지 번호가 매겨져 있다.

이어지는 $m$개 줄에는 정수 두 개 $u_i$, $v_i$ ($1\leq u_i<v_i\leq n$)가 주어지며, 이는 정점 $u_i$와 $v_i$가 간선으로 연결되어 있다는 뜻이다. 쌍 $(u_i,v_i)$는 모두 서로 다르다.

다음 두 줄에는 순서대로 색칠 $c_b$와 $c_s$가 주어진다. 각 색칠은 $n$ 이하의 양의 정수 $n$개로 이루어지며, $i$번째 수가 정점 $i$의 색이다. $c_b$는 아름다운 색칠이고, $c_s$는 똑똑한 색칠이다.

아름다우면서 동시에 똑똑한 색칠이 존재하면 첫 줄에 "TAK"(폴란드어로 '예')를 출력한다. 둘째 줄에는 입력과 같은 형식으로 그런 색칠의 정수 $n$개를 출력한다. 가능한 색칠이 여러 개라면 그중 아무거나 출력해도 된다.

존재하지 않으면 "NIE"(폴란드어로 '아니오')만 한 줄에 출력한다.