通过 DMG-04（连接线）连接的两台 Game Boy 系统。来自 KoS 的公有领域照片。

学校里的孩子们沉迷于一款名为《宝可梦》（Pokémon）的收集口袋妖怪的新电子游戏。他们的目标是通过完成宝可梦图鉴来“收服所有宝可梦”，这意味着他们想要捕捉到每种宝可梦。通常，他们通过玩游戏、遭遇宝可梦并用精灵球捕捉它们来实现这一目标。

宝可梦游戏发布了不同的版本。每个版本都包含若干种宝可梦，其中一些是该版本独占的。例如，只有《宝可梦 蓝色版》（版本 1）才能遇到名为喵喵（Meowth）的宝可梦。因此，拥有《宝可梦 红色版》（版本 2）的孩子无法捕捉喵喵，必须与拥有喵喵的朋友进行交换才能填满图鉴。这位朋友可能自己拥有《宝可梦 蓝色版》，也可能是通过其他交换得到了喵喵。

你的任务是将宝可梦游戏版本分发给孩子们，使得通过朋友之间的交换，每个孩子最终都能收集到每种宝可梦至少一只。每个孩子恰好获得一个宝可梦游戏版本。每个版本都附带了足够数量的该版本宝可梦（包括独占和非独占的），以确保交换总是可行的。

输入格式

输入包含以下内容：

• 第一行包含三个整数 $n$、$m$ 和 $k$：孩子的数量 $n$（$1 \le n \le 100\,000$）、朋友关系的数量 $m$（$1 \le m \le 200\,000$）以及不同游戏版本的数量 $k$（$1 \le k \le 100\,000$）。
• 接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$（$1 \le a < b \le n$），表示 $a$ 和 $b$ 是朋友。

输出格式

输出 $n$ 个整数，每个孩子一个，表示该孩子应该获得哪个游戏版本。如果所有孩子都能通过与朋友进行任意次数的交换来填满他们的图鉴，则你的输出将被视为正确。

如果存在多个有效解，你可以输出其中任意一个。

如果不存在任何能让所有孩子填满图鉴的游戏版本分配方案，则输出 impossible。

样例

输入格式 1

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

输出格式 1

1 2 1 2 1 2 1 2

输入格式 2

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

输出格式 2

impossible

输入格式 3

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

输出格式 3

1 2 3 4 5 6 7 8