灰色外星人 E.T. 和 Ste 是这个星系的共同统治者。他们统治的星系包含 $n$ 个行星，由 $m$ 个跃迁通道连接。每个跃迁通道都是单向的。这些跃迁通道不形成任何环——在离开一个行星后，不可能通过沿着一系列跃迁通道返回该行星（否则必须使用普通的太空旅行，那要慢得多）。此外，每个行星最多有 $k$ 个指向它的入站跃迁通道。

统治星系并非易事，因此 E.T. 和 Ste 招募了 $k + 1$ 位执政官来协助他们。E.T. 和 Ste 将把每位执政官分配到一些行星上，前提是没有任何一位执政官被分配到两个由跃迁通道直接相连的行星上。通过让执政官管理整个星系的行星，他们希望这能促进一种更全面的治理方式。

E.T. 和 Ste 计划在他们的星际旅行中想出如何分配执政官。不幸的是，他们遭遇了意料之外的磁场，导致他们的星系跃迁通道地图损坏了。结果，所有跃迁通道的方向都丢失了。E.T. 和 Ste 现在必须仅凭这张损坏的地图来完成执政官的分配。

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$0 \le m \le 5 \cdot 10^5$，$m \le \frac{n(n-1)}{2}$，$0 \le k \le n - 1$），分别表示行星的数量、跃迁通道的数量，以及星系中任意行星最多可拥有的入站跃迁通道数量。

接下来的 $m$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x < y \le n$），表示在行星 $x$ 和行星 $y$ 之间存在一个跃迁通道（由于地图损坏，其方向已丢失，可能是从 $x$ 到 $y$，也可能是从 $y$ 到 $x$）。

所有跃迁通道都是两两不同的。数据保证在地图损坏之前，跃迁通道不形成环，且每个行星最多有 $k$ 个入站跃迁通道。

输出格式

这 $k + 1$ 位执政官的编号为 $1$ 到 $k + 1$。

输出 $n$ 个空格分隔的介于 $1$ 到 $k + 1$ 之间的整数，其中第 $i$ 个整数表示分配给行星 $i$ 的执政官编号。某些执政官可能未被分配到任何行星。

如果存在多种有效的分配方案，输出其中任意一种即可。可以证明，在给定的约束条件下，总是存在至少一种有效的分配方案。

样例

输入样例 1

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

输出样例 1

1 1 2 1 3 1

输入样例 2

5 2 1
1 2
3 4

输出样例 2

1 2 2 1 2