CF1218G Alpha planetary system

阿尔法星系中的三颗行星 $X$、$Y$ 和 $Z$ 上居住着高度发达的文明。这些行星上的太空港通过星际穿梭航班相互连接。航班调度员需要为每一条现有的穿梭航线决定 $1$、$2$ 或 $3$ 个往返航班的数量。由于阿尔法居民极力反对对称性，有一条严格的规定：任何由穿梭航线连接的两个太空港，其航班数量必须不同。 对于每一对已连接的太空港，你的目标是为每条穿梭航线指定 $1$、$2$ 或 $3$ 中的一个数字，使得每一对已连接的太空港的总航班数都不相同。 你可以假设： 1）每个行星上至少有一个太空港。 2）只有不同行星上的太空港之间才有穿梭航班。 3）对于任意两个太空港，都存在一系列穿梭航班可以实现它们之间的互通。 4）任意两太空港之间至多只有一条穿梭航线。

第一行输入一个整数 $N$ $(3 \leq N \leq 100\,000)$，表示太空港的总数。第二行输入一个整数 $M$ $(2 \leq M \leq 100\,000)$，表示穿梭航线的数量。 第三行包含 $N$ 个字符，每个字符属于集合 $\{X, Y, Z\}$。第 $i$ 个字符表示第 $i$ 个太空港所在的行星。例如，"XYYXZZ" 表示第 $0$ 和第 $3$ 个太空港位于行星 $X$，第 $1$ 和第 $2$ 个太空港位于 $Y$，第 $4$ 和第 $5$ 个太空港位于 $Z$。 从第四行开始，每行包含两个用空格分隔的整数，表示一条穿梭航线连接的两个太空港的编号。例如，"12 15" 表示在第 $12$ 号和第 $15$ 号太空港之间有一条穿梭航线。

输出与输入中穿梭航线顺序相同的 $M$ 行，每行在原有的两个太空港编号后，增加一个属于 $\{1, 2, 3\}$ 的数字，表示这条航线的航班数量。

由 ChatGPT 4.1 翻译