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

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.