410560: GYM104049 L Loid Forger
Description
Twilight has been mistaken for a real forger, and now must work in a metal factory to conceal his identity.
For his job, Twilight needs to melt down metals in a smeltery. Each smeltery can be set to a specific temperature, and each metal has a temperature range that the smeltery must satisfy for the metal to melt properly.
To speed up the process, multiple metals can be placed into the smeltery at the same time. However, some metals will alloy together when melted, so those cannot be melted together.
Due to his extensive background, Twilight has been given access to two smelteries which he can use. Since Twilight is busy and has spy things (a family) to attend to, he'd like to set the temperature for the smelteries and place the metals in all at once. Help Twilight!
InputThe first line contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n,m \leq 10^5$$$).
Then, $$$n$$$ lines follow. The $$$i$$$th line contains two integers, $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq 10^9$$$), signifying that the temperature of the smeltery for metal $$$i$$$ must be in the range $$$[l_i, r_i]$$$.
Finally, $$$m$$$ lines follow, each containing two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a,b \leq n$$$, $$$a \not= b$$$), meaning that metals $$$a$$$ and $$$b$$$ will alloy together when placed in the same smeltery.
OutputIf it is not possible for Twilight to smelt all metals at once, output "No".
Otherwise, output "Yes" on the first line.
On the second line, you should output two integers $$$t_1$$$ and $$$t_2$$$, representing the temperature settings of the first and second smeltery, respectively.
On the third line, you should output $$$n$$$ integers, representing which smeltery each metal should go in. Specifically, if the $$$i$$$th integer is $$$1$$$, then metal $$$i$$$ should be placed in the first smeltery. Similarly, if the $$$i$$$th integer is $$$2$$$, then metal $$$i$$$ should be placed in the second smeltery.
ExamplesInput3 1 5 15 10 20 10 40 1 3Output
Yes 12 30 1 1 2Input
3 0 10 20 30 40 50 60Output
No