Серёжа — современный художник, поэтому в своих композициях он использует 3D-принтер. В данный момент Серёжа придумал идею следующей композиции. Он напечатает n разноцветных пластиковых брусков и попытается расположить эти бруски горизонтально один над одним (бруски можно считать горизонтальными отрезками на плоскости, имеющими ненулевую длину и лежащими на попарно различных прямых, параллельных оси абсцисс), но сделать это следует с учетом соотношений цветов (Серёжа же всё-таки художник!). Соотношения бывают двух видов: соотношение предшествования (тип A) и соотношение пересечения (тип B).
Если для двух брусков i и j есть соотношение типа A, то брусок i должен лежать строго левее бруска j (то есть координата по оси абсцисс любой точки бруска i должна быть строго левее координаты по оси абсцисс любой точки бруска j).
Соотношение типа B между брусками i и j означает, что данные бруски должны иметь хотя бы по одной точке, не являющейся границей бруска, проекции которых на ось абсцисс совпадают.
Если между двумя брусками нет ни соотношения А, ни соотношения B, то они могут располагаться друг относительно друга в любом порядке.
Помогите Серёже найти идеальные координаты по оси абсцисс для своих брусков или определить, что это невозможно. В случае успеха своей композиции он, может быть, даже поделится с вами гонораром!
В первой строке задано три целых числа через пробел: n, a и b (1 ≤ n ≤ 105, 0 ≤ a, b ≤ 105) — количество брусков, а также количество ограничений первого и второго типа соответственно.
В следующих a строках указаны пары целых чисел fa[i] и sa[i] (1 ≤ fa[i], sa[i] ≤ n, fa[i] ≠ sa[i]) — номера брусков, для которых должно выполняться соотношение типа А.
В следующих b строках указаны пары целых чисел fb[i] и sb[i] (1 ≤ fb[i], sb[i] ≤ n, fb[i] ≠ sb[i]) — номера брусков, для которых должно выполняться соотношение типа B.
Если расположения брусков, удовлетворяющего данным требованиям, не существует, выведите в единственной строке «NO» (без кавычек).
В противном случае в первой строке выведите «YES» (без кавычек). Далее, для каждого из n брусков на отдельной строке выведите два целых числа li и ri (0 ≤ li < ri ≤ 109) — координаты левого и правого концов i-го бруска по оси абсцисс в удовлетворяющем всем требованиям расположении.
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
