著名的亿万富翁 Bajtelon 刚刚买下了一个社交网络。他很快意识到，为了让这项投资物有所值，他必须进行一系列改革，以吸引新的广告商。首先，他试图通过在网站上推广关于当前“热门话题”的极端观点，来为他的网络制造更多声量。

该社交网络中有 $n$ 名用户，他们之间存在 $m$ 条对称的友谊关系。每位用户可以对“热门话题”持有 $1$ 到 $k$ 之间的某种观点（为简化起见，观点用 $1$ 到 $k$ 的数字编号，其中 $k$ 表示完全赞同，$1$ 表示完全反对）。

Bajtelon 可以通过精心挑选的广告，说服每位用户接受他所选择的观点（观点是为每位用户单独选择的）。他希望最终达成以下目标： 每位用户看到的邻居观点都与自己的观点不同，但很接近（具体来说：邻居的观点与他自己的观点之差的绝对值恰好为 $1$）； 持有极端观点（$1$ 或 $k$）的人数尽可能多。

请帮助他选择应该分配给每位用户的观点。

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$3 \le n \le 200$，$0 \le m \le n(n-1)/2$，$3 \le k \le n$），分别表示网络中的用户数、友谊关系数和观点数量。网络中的用户编号为 $1$ 到 $n$。

接下来的 $m$ 行描述了友谊关系；每行包含两个整数 $a$ 和 $b$（$1 \le a, b \le n, a \neq b$），表示编号为 $a$ 和 $b$ 的用户是社交网络中的好友。每条友谊关系不会被重复给出。

输出格式

如果无法按照 Bajtelon 的要求分配观点，请输出一行，包含单词 NIE。

否则，输出应包含两行。第一行应包含一个整数 $s$，表示在某种合法的观点分配方案下，持有观点 $1$ 或 $k$ 的用户的最大数量。

第二行应包含一个由 $n$ 个整数组成的序列，这些整数在 $[1, k]$ 范围内，并用空格分隔；第 $i$ 个数字表示在某种合法的分配方案中，用户 $i$ 的观点。在该序列中，必须恰好有 $s$ 个人持有观点 $1$ 或 $k$。

样例

输入格式 1

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

输出格式 1

5
2 3 4 3 1 1 4 4

说明

图示说明：图中的点表示网络用户，连线表示友谊关系。点旁边的数字表示用户编号，括号内的数字表示其最终观点。共有 5 人持有极端观点（1 或 4）。

输入格式 2

3 3 3
1 2
2 3
3 1

输出格式 2

NIE

子任务

测试集分为以下子任务。每个子任务的测试用例由一组或多组独立的测试组组成。

如果可以按照 Bajtelon 的要求分配观点（即答案不是 NIE），而你的程序仅正确输出了输出的第一行，则该测试点将获得 50% 的分数。特别地，为了获得该测试点 50% 的分数，无需输出第二行。