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.
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
Name |
---|