P14501 [NCPC 2025] Gotta Trade Some of 'Em

:::align{center}  两台通过 DMG-04（连接线）连接的 Game Boy 主机。KoS 提供的公有领域照片。 :::

学校里的孩子们迷上了一款新的口袋妖怪收集类电子游戏 **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（包括独占与非独占），确保交易随时可行。

输入包含： - 一行三个整数 $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$ 互为朋友。

输出 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个孩子应获得哪个游戏版本。只要所有孩子都能通过任意次数的朋友间交易填满 Pokédex，你的输出就会被判定为正确。 如果存在多个合法方案，你可以输出任意一个。 如果不存在任何分配方式可以使所有孩子填满 Pokédex，则输出 `impossible`。

翻译由 ChatGPT-5 完成