#P17069. [PA 2015 Final]Kolorowania

    ID: 16270 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-顶点着色局部修复不变量分析队列异或抵消增量维护

[PA 2015 Final]Kolorowania

题目描述

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

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

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

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

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

输入格式

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

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

最后两行分别描述了着色 clc_{l} 和 cmc_{m}。每个着色的描述由 nn 个不大于 nn 的正整数组成:其中的第 ii 个数代表第 ii 号顶点的颜色。保证 clc_{l} 是漂亮的,且 cmc_{m} 是聪明的。

输出格式

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

如果不存在这样的着色,请在输出 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