5030. 「POI 2022/2023 R3」社交网络

题目译自 XXX Olimpiada Informatyczna – III etap Siec spolecznosciowa

题目描述

今天是 Bajtazar 的生日，$k$ 位宾客齐聚生日派对。Bajtazar 早有准备，烤了一块巨大的蛋糕。现在，他需要将蛋糕切分给每位宾客和自己享用！

著名亿万富翁 Bajtelon 最近收购了一家社交网络。他很快意识到，要让投资盈利，必须进行一系列改革，吸引更多广告商。首要任务是通过推广极端观点，在平台上掀起关于热门话题的热议，制造更多话题效应。

平台上有 $n$ 名注册用户，彼此间有 $m$ 条对称的友谊关系。每位用户可持有 $k$ 种观点之一（为简化，观点编号为 $1$ 至 $k$，其中 $1$ 表示完全反对，$k$ 表示完全赞成）。

Bajtazar 可以通过精准广告，引导每位用户持有他指定的观点（为每位用户单独选择）。他希望最终实现：

• 每位用户在其好友中看到不同但相近的观点（具体为：好友的观点与其自身观点恰好相差 $1$）。
• 持有极端观点（$1$ 或 $k$）的用户数量尽可能多。

请帮助他为每位用户分配合适的观点。

输入格式

第一行包含三个整数 $n$, $m$, $k$ ($3 \leq n \leq 200$, $0 \leq m \leq n(n-1)/2$, $3 \leq k \leq n$)，分别表示用户数量、友谊关系数量和观点种类数量。用户编号为 $1$ 至 $n$。

接下来的 $m$ 行描述友谊关系，每行包含两个整数 $a$, $b$ ($1 \leq a, b \leq n$, $a \neq b$)，表示编号为 $a$ 和 $b$ 的用户互为好友。每条友谊关系仅出现一次。

输出格式

若无法按 Bajtelon 的要求分配观点，输出一行，包含一个字符串 NIE。

否则，输出两行：

• 第一行包含一个整数 $s$，表示在某种合法观点分配下，持有观点 $1$ 或 $k$ 的最大用户数。
• 第二行包含 $n$ 个整数，范围在 $[1, k]$，表示某合法分配中用户 $1$ 至 $n$ 的观点。序列中恰有 $s$ 个用户持有观点 $1$ 或 $k$。

样例

输入

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

输出

5
2 3 4 3 1 1 4 4

图中点表示用户，线表示友谊关系。点旁数字为用户编号，括号中数字为其最终对热门话题的观点。有 $5$ 名用户持有极端观点（$1$ 或 $4$）。

附加样例

• $n=m=101$, $k=3$，友谊关系构成环，结果 NIE。
• $n=m=100$, $k=4$，友谊关系构成环，结果 $50$。
• $n=101$, $m=1$, $k=n$，结果 $100$。
• $n=63$, $m=62$, $k=6$，每位用户 $i \leq 31$ 与用户 $2i$ 和 $2i+1$ 互为好友，结果 $42$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
1	$k=3$	15
2	$n \leq 20$
3	$k=4$	30
4	无附加限制	40

---

时间限制：1000 - 5000 ms
内存限制：512 MiB