29124번 - Ломать --- не строить 스페셜 저지다국어채점 준비 중

Все ушли из дома, и теперь Альфу нечем заняться. Но тут он увидел на стене карту Лос-Анджелеса и решил ее поизучать. Больше всего Альфу интересны автомобильные дороги, ведь на его родной планете Мелмак их не было --- все автомобили там уже давным-давно летают.

Дорожная система Лос-Анджелеса представляет собой набор из $n$ точек общего положения на плоскости, между которыми проведены отрезки --- двусторонние дороги. Причем из каждой точки проведено ровно два отрезка --- это порядком удивило Альфа. Перерисовав дорожную систему себе на листок, Альф решил удалить из нее какие-то дороги, ведь он так любит все ломать! Но он не хочет удалять любые дороги. Он хочет у каждой точки удалить ровно одну дорогу, исходящую из нее, так, чтобы после этого никакие две дороги не пересекались. Альф считает, что дороги пересекаются, если у них есть общая точка, отличная от их концов.

Альф очень любопытный, помогите ему узнать, можно ли сделать то, что он хочет.

В первой строке входного файла содержится число $n$ ($3 \le n \le 500$) --- количество точек на плоскости.

В $i$-й из следующих $n$ строк содержатся два целых числа $x_i, y_i$ ($|x_i|, |y_i| \le 10^9$) --- координаты $i$-й точки.

Далее дано еще $n$ строк, в $i$-ой из которых записано два числа $v, u$ ($1 \le v, u \le n, v \ne u$) --- номера точек, с которыми $i$-я точка соединена отрезками.

Гарантируется, что точки общего положения --- никакие две точки не совпадают и никакие три не лежат на одной прямой. Также все отрезки имеют ненулевую длину.

Если нельзя так у каждой точки удалить ровно один отрезок, в единственной строке выходного файла выведите NO. Иначе, в первой строке выходного файла выведите YES, а в $i$-й из следующих $n$ строк выведите число $x$ ($1 \le x \le 2$) --- какой из отрезков у вершины номер $i$ надо удалить. Отрезок в вершину $v$ имеет номер 1, отрезок в вершину $u$ --- номер 2.