Description

学校里的孩子们迷上了一款新的口袋妖怪收集类电子游戏 Pokémon。他们的目标是通过完成 Pokédex 来 “全部捕获”，也就是说，他们希望能抓到每一种 Pokémon。通常，他们会通过游玩游戏、遇见 Pokémon、并用 Pokéball 将其捕捉来实现这一目标。

Pokémon 游戏会发行多种不同版本。每个版本都包含一些 Pokémon，其中部分 Pokémon 是该版本的独占。例如，只有 Pokémon Blue（版本 $1$）可以遇到一种名为 Meowth 的 Pokémon。因此，一个拥有 Pokémon Red（版本 $2$）的孩子无法捕捉到 Meowth，只能通过与朋友交换来填满 Pokédex。而这个朋友可能自己拥有 Pokémon Blue，或是通过其他交易获得了 Meowth。

你的任务是为孩子们分配 Pokémon 游戏版本，使得他们能够通过与朋友间的交易，最终每个人都能至少收集到每一种 Pokémon。每个孩子恰好获得一个 Pokémon 游戏版本。每个版本都提供足够数量的 Pokémon（包括独占与非独占），确保交易随时可行。

Input Format

输入包含：

• 一行三个整数 $n$、$m$ 和 $k$：表示孩子人数 $n$（$1 \leq n \leq 100\,000$），朋友关系数 $m$（$1 \leq m \leq 200\,000$），以及游戏版本数 $k$（$1 \leq k \leq 100\,000$）。
• 接下来 $m$ 行，每行两个整数 $a$ 和 $b$，满足 $1 \leq a < b \leq n$，表示孩子 $a$ 和孩子 $b$ 互为朋友。

Output Format

输出 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个孩子应获得哪个游戏版本。只要所有孩子都能通过任意次数的朋友间交易填满 Pokédex，你的输出就会被判定为正确。

如果存在多个合法方案，你可以输出任意一个。

如果不存在任何分配方式可以使所有孩子填满 Pokédex，则输出 impossible。

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

1 2 1 2 1 2 1 2

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

impossible

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

1 2 3 4 5 6 7 8

Hint

翻译由 ChatGPT-5 完成