410560: GYM104049 L Loid Forger

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. Loid Forgertime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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!

Input

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

Output

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

ExamplesInput
3 1
5 15
10 20
10 40
1 3
Output
Yes
12 30
1 1 2
Input
3 0
10 20
30 40
50 60
Output
No

加入题单

算法标签: