409330: GYM103485 L A tale of two cities

One of the most famous stories of the ancient Egypt is the "Tale of two brothers". In this tale, the trust between the two sons of the pharaoh Seti II, Anpu and Bata, is tested by the mischievous behaviour of Anpu's wife. Currently, the Myths Collector Association (ACM in their language) is conducting an excavation, under the supervision of Marcio "the intrepid" Himura, in Thebes near the Nile river. His team has found a papyrus that tells an earlier story of this pharaoh related to his two sons.

Seti II was the ruler of the Egyptian empire during the period known as the "New Kingdom". In this tale, Seti II decided to divide his land in two parts, after the birth of Bata. The empire consists of $$$N$$$ cities. The pharaoh designated two cities, Memphis and Giza, as the capitals of these new kingdoms. Moreover, the kingdom containing Memphis (resp. Giza) must contain $$$X$$$ cities (resp. $$$Y$$$ cities). Since Seti II did not want to create any dependency or conflict between these new kingdoms, one last requirement was the following: from each capital the ruler may visit any city inside the corresponding kingdom without passing through a city from the other kingdom.

Alongside the papyrus containing the story, Marcio also found a map, presumably of the Egyptian empire during the reign of Seti II, that indicates the locations of the cities and roads between them. Moreover, this map also contains the numbers $$$X$$$ and $$$Y$$$ described above. Marcio is curious whether such tale may be true. After analyzing the map, Marcio also observed the following. In the former empire, for any three cities, say $$$A$$$, $$$B$$$, and $$$C$$$, there is a route between $$$A$$$ and $$$B$$$ that does not contain $$$C$$$.

Marcio needs to supervise the excavations in Thebes, but considers the verification of this tale a major discovery. So he designated you to solve this mystery. In case there exists a way to divide the Egyptian empire as described above, Marcio also asked you to give a way to do it (this will serve as a certificate for the ACM).

The first line contains $$$N$$$ and $$$M$$$, the number of cities and roads in the map, respectively. Each city is numbered from $$$1$$$ to $$$N$$$. The following $$$M$$$ lines describe a road using two space-separated integers. After that, we have two lines. The first one contains two integers, the number corresponding to the city of Memphis and the number $$$X$$$ described in the statement. The second line contains two integers, the number corresponding to the city of Giza and the number $$$Y$$$ described in the statement.

• $$$3 \leq N \leq 10^5$$$
• $$$3 \leq M \leq 10^6$$$
• $$$1 \leq X, Y \leq N - 1$$$, $$$X + Y = N$$$
• $$$1 \leq s, t \leq N$$$, $$$s \neq t$$$

In the first line print 'Y' if we can divide the Egyptian empire in two kingdoms as described by the tale, otherwise print 'N'. If the division is possible, in the next line print $$$N$$$ space-separated integers. Each of these integers must be either $$$0$$$ or $$$1$$$. If the $$$i$$$-th integer is $$$0$$$ it means that the city numbered $$$i$$$ belongs to the kingdom of Memphis, otherwise it belongs to the kingdom of Giza. If there are multiple answers, print any of them.

10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 1
3 2
8 8

Y
1 0 0 1 1 1 1 1 1 1