阿尔法行星系统内的三颗行星$$$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)$$$ 表示往返航班的数量。
第三行包含来自集合 $$$\{X, Y, Z\}$$$ 的 $$$N$$$ 个字符。 $$$I^{th}$$$ 位置上的字母表示太空港 $$$I$$$ 位于哪个行星上。例如,“XYYXZZ”表示太空港 $$$0$$$ 和 $$$3$$$ 位于行星 $$$X$$$,太空港 $$$1$$$ 和 $$$2$$$ 位于 $$$Y$$$,太空港 $$$4$$$ 和 $$$5$$$ 位于 $$$Z$$$。
从第四行开始,每行包含两个由空格分隔的整数。这些数字是小于 $$$N$$$ 的自然数,表示所连接的太空港的编号。例如,“$$$12\ 15$$$”表示在太空港 $$$12$$$ 和 $$$15$$$ 之间有航天飞机飞行。
输出
与输入中不同行中的航天飞机航班的表示相同,但还包含 $$$\{1, 2, 3\}$$$ 集合中的第三个数字,代表这些航天港之间的航天飞机航班数量。
示例
输入 #1
10 15 XXXXYYYZZZ 0 4 0 5 0 6 4 1 4 8 1 7 1 9 7 2 7 5 5 3 6 2 6 9 8 2 8 3 9 3
输出 #1
0 4 2 0 5 2 0 6 2 4 1 1 4 8 1 1 7 2 1 9 3 7 2 2 7 5 1 5 3 1 6 2 1 6 9 1 8 2 3 8 3 1 9 3 1