CF1218G.Alpha planetary system

Three planets $X$, $Y$ and $Z$ within the Alpha planetary system are inhabited with an advanced civilization. The spaceports of these planets are connected by interplanetary space shuttles. The flight scheduler should decide between $1$, $2$ and $3$ return flights for every existing space shuttle connection. Since the residents of Alpha are strong opponents of the symmetry, there is a strict rule that any two of the spaceports connected by a shuttle must have a different number of flights.

For every pair of connected spaceports, your goal is to propose a number $1$, $2$ or $3$ for each shuttle flight, so that for every two connected spaceports the overall number of flights differs.

You may assume that:

1. Every planet has at least one spaceport

2. There exist only shuttle flights between spaceports of different planets

3. For every two spaceports there is a series of shuttle flights enabling traveling between them

4. Spaceports are not connected by more than one shuttle

Alpha行星系内有三颗行星 $X$、$Y$ 和 $Z$，其上居住着一个高度发达的文明。这些行星上的航天港通过星际航天飞机相互连接。航班调度员需为每条已有的航天飞机航线决定往返航班次数：只能选择 $1$、$2$ 或 $3$ 次。由于Alpha星居民强烈反对对称性，因此存在一条严格规则：任意两个由航天飞机直接连接的航天港，其各自的总航班次数必须不同。

对于每一对彼此连接的航天港，你的任务是为每条航天飞机航线指定一个数字 $1$、$2$ 或 $3$，使得任意两个直接相连的航天港，其各自关联的航班总次数互不相同。

你可以假设：

1. 每颗行星至少拥有一个航天港；
2. 航天飞机仅在不同行星的航天港之间运行；
3. 对于任意两个航天港，均存在一系列航天飞机航线，使其可以互相抵达（即整个航天港网络连通）；
4. 任意两个航天港之间至多只有一条航天飞机航线连接。

The first row of the input is the integer number $N$ $(3 \leq N \leq 100 000)$, representing overall number of spaceports. The second row is the integer number $M$ $(2 \leq M \leq 100 000)$ representing number of shuttle flight connections.

Third row contains $N$ characters from the set ${X, Y, Z}$. Letter on $I^{th}$ position indicates on which planet is situated spaceport $I$. For example, "XYYXZZ" indicates that the spaceports $0$ and $3$ are located at planet $X$, spaceports $1$ and $2$ are located at $Y$, and spaceports $4$ and $5$ are at $Z$.

Starting from the fourth row, every row contains two integer numbers separated by a whitespace. These numbers are natural numbers smaller than $N$ and indicate the numbers of the spaceports that are connected. For example, "$12\ 15$" indicates that there is a shuttle flight between spaceports $12$ and $15$.

输入的第一行是整数 $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$。

从第四行开始，每一行包含两个由空格分隔的整数。这两个数均为小于 $N$ 的自然数，表示相互连通的两个空间港的编号。例如，"12 15" 表示空间港 $12$ 与空间港 $15$ 之间存在一趟穿梭机航班。

The same representation of shuttle flights in separate rows as in the input, but also containing a third number from the set ${1, 2, 3}$ standing for the number of shuttle flights between these spaceports.

与输入中相同的航天飞机航班表示方式（即每行表示一次航班），但还需包含第三个数字，该数字属于集合 $\{1, 2, 3\}$，表示这两座航天港之间的航天飞机航班次数。