[AdditionalFile5636.zip](file://AdditionalFile5636.zip?type=additional_file)

#5636. 「PA 2015 Final」Kolorowania

标签: 传统 | 时间限制: 10000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2015 Final Kolorowania

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

如果对于每个 $v \in V$，都有 $c(v) \in \{1, 2, \ldots, k\}$，则称着色 $c$ 是漂亮的。换句话说，漂亮的着色只使用从 $1$ 到 $k$ 的整数作为颜色。

如果对于每个 $v \in V$，都存在一个 $w \in V$（且 $w \neq v$）使得 $c(v) = c(w)$，则称着色 $c$ 是聪明的。换句话说，聪明的着色中，每种被使用的颜色都至少在两个不同的顶点上出现。

Bajtazar 正在为他的图寻找一种合适的着色。他曾经找到过一种漂亮的着色 $c_{l}$，但他觉得它太简单且缺乏挑战性。另一次，他成功找到了一种聪明的着色 $c_{m}$，但过了一段时间后，他已经厌倦得不想再看到它了。

Bajtazar 已经不抱希望能在有生之年遇到一种既漂亮又聪明的着色了。你能给他一个惊喜并找到这样一种着色吗？

输入格式

输入的第一行包含三个整数 $n, m, k$ $(1 \leq k \leq n \leq 200000, 0 \leq m \leq 200000)$。其中 $k$ 定义了哪些着色被视为漂亮的，而 $n$ 和 $m$ 分别是 Bajtazar 图中顶点的数量和边的数量。图的顶点编号为从 $1$ 到 $n$。

接下来的 $m$ 行描述了图的边。其中的第 $i$ 行包含两个整数 $u_{i}, v_{i}$ $(1 \leq u_{i} < v_{i} \leq n)$，表示编号为 $u_{i}$ 和 $v_{i}$ 的顶点之间存在一条边。输入中不会出现重复的边 $(u_{i}, v_{i})$。

最后两行分别描述了着色 $c_{l}$ 和 $c_{m}$。每个着色的描述由 $n$ 个不大于 $n$ 的正整数组成：其中的第 $i$ 个数代表第 $i$ 号顶点的颜色。保证 $c_{l}$ 是漂亮的，且 $c_{m}$ 是聪明的。

输出格式

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

如果不存在这样的着色，请在输出 NIE。

样例

输入

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

输出

TAK
1 2 1 2 3 3 3 3