B'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 <= q N <= q 100 000) , representing overall number of spaceports. The second row is the integer number M (2 <= q M <= q 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 rep'...