设 $G = (V, E)$ 为一个无向图。若对于每一条边 $(u, v) \in E$ 都有 $c(u) \neq c(v)$，则称函数 $c : V \to \mathbb{N}$ 为一个着色方案。

若对于每个 $v \in V$ 都有 $c(v) \in \{1, 2, \dots, k\}$，则称着色方案 $c$ 是“漂亮的”。换句话说，如果着色方案 $c$ 仅使用 $1$ 到 $k$ 之间的整数作为颜色，则它是漂亮的。

若对于每个 $v \in V$ 都存在一个 $w \in V$ 且 $w \neq v$，使得 $c(v) = c(w)$，则称着色方案 $c$ 是“聪明的”。换句话说，如果着色方案 $c$ 中使用的每种颜色至少被使用了两次，则它是聪明的。

Bajtazar 正在为他的图寻找合适的着色方案。他曾经找到过一个漂亮的着色方案 $c_l$，但觉得它太简单且缺乏挑战性。另一次，他成功找到了一个聪明的着色方案 $c_m$，但过了一段时间后他便不再喜欢它了。

Bajtazar 已经不抱希望能在他的图上同时找到既漂亮又聪明的着色方案。你能给他一个惊喜并找到这样的着色方案吗？

输入格式

输入的第一行包含三个整数 $n, m, k$ ($1 \le k \le n \le 200\,000$, $0 \le m \le 200\,000$)。数字 $k$ 描述了我们认为哪些着色方案是漂亮的，$n$ 和 $m$ 分别是图的顶点数和边数。图的顶点编号为 $1$ 到 $n$。

接下来的 $m$ 行描述了图的边。第 $i$ 行包含两个整数 $u_i, v_i$ ($1 \le u_i < v_i \le n$)，表示顶点 $u_i$ 和 $v_i$ 之间有一条边。输入中不会出现重复的边 $(u_i, v_i)$。

接下来的两行分别描述了着色方案 $c_l$ 和 $c_m$。着色方案的描述由 $n$ 个不大于 $n$ 的正整数组成：第 $i$ 个数字表示编号为 $i$ 的顶点的颜色。

着色方案 $c_l$ 是漂亮的，着色方案 $c_m$ 是聪明的。

输出格式

如果存在一种既聪明又漂亮的图着色方案，请在第一行输出 TAK，并在第二行输出 $n$ 个整数来描述该着色方案。描述的格式应与输入中给出的着色方案格式相同。

如果不存在这样的着色方案，请在唯一的一行输出 NIE。

样例

样例输入 1

8 7 3
1 2
2 3
3 4
1 5
1 6
1 7
1 8
1 2 3 2 2 2 2 2
1 2 4 1 2 3 4 3

样例输出 1

TAK
1 2 1 2 3 3 3 3