402193: GYM100694 C Modern Art

Sergey is a modern artist who uses 3D printer in his works. He has just come up with the idea of his next work. He is going to print n colored bars and place them horizontally one over another (the bars can be considered as horizontal segments on the plane, which have positive lengths and belong to pairwise distinct lines parallel to X-axis), but he also wants to satisfy some conditions (he is an artist, after all). There are two types of conditions: precendence (type A) and intersection (type B).

If there is a precendence condition between two bars i and j, the bar i must be placed strictly to the left of the bar j (that is, X-coordinate of any point of bar i must be strictly less than X-coordinate of any point of bar j).

Intersection condition between bars i and j means that both bars must have at least one point which is not an end such that the X-coordinates of these points are equal.

If there are no conditions between some two bars, they can be placed in any order relatively to each other.

Help Sergey to find perfect X-coordinates for his bars or say that it's impossible. If his work is successful he might even share his earnings with you!

The first line contains three space-separated integers n, a and b (1 ≤ n ≤ 10⁵, 0 ≤ a, b ≤ 10⁵) — the number of bars and the numbers of conditions of type A and type B.

Each of the next a lines contains two space-separated integers f_a[i] and s_a[i] (1 ≤ f_a[i], s_a[i] ≤ n, f_a[i] ≠ s_a[i]) — the indices of bars for which the condition of type A must be satisfied.

Each of the next b lines contains two space-separated integers f_b[i] and s_b[i] (1 ≤ f_b[i], s_b[i] ≤ n, f_b[i] ≠ s_b[i]) — the indices of bars for which the condition of type B must be satisfied.

If the required arrangement of bars doesn't exist, write «NO» (without quotes).

Otherwise in the first line write «YES» (without quotes). Next, write n lines, the i-th of which should contain two integers l_i and r_i (0 ≤ l_i < r_i ≤ 10⁹) — the X-coordinates of the left and right ends of the i-th bar.

4 2 1
1 2
2 3
3 4

YES
0 1
2 3
4 6
5 7

3 2 0
1 2
2 1

NO