Alpha planetary system
Description
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
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$.
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.
Input
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$.
Output
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.
Samples
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
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