D. Муравьи
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
768 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть дерево из $$$n$$$ вершин, в котором живут $$$m$$$ муравьёв. Каждый муравей имеет свой собственный цвет. У $$$i$$$-го муравья есть две любимые пары вершин: ($$$a_i, b_i$$$) и ($$$c_i, d_i$$$). Вам нужно сказать, можно ли раскрасить рёбра дерева в $$$m$$$ цветов так, чтобы каждый муравей мог ходить между вершинами какой-то из своих любимых пар, используя только рёбра своего цвета; и если можно, то вывести, какую из пар будет использовать каждый муравей.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — количество вершин.

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$), означающие, что есть ребро между $$$u_i$$$ и $$$v_i$$$.

Следующая строка содержит одно целое число $$$m$$$ ($$$1 \leq m \leq 10^4$$$) — количество муравьёв.

Каждая из следующих $$$m$$$ строк содержит четыре целых числа $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ и $$$d_i$$$ ($$$1 \leq a_i, b_i, c_i, d_i \leq n$$$, $$$a_i \neq b_i, c_i \neq d_i$$$), означающие, что пары вершин ($$$a_i$$$, $$$b_i$$$) и ($$$c_i$$$, $$$d_i$$$) являются любимыми для $$$i$$$-го муравья.

Выходные данные

Выведите «NO» (без кавычек), если искомая раскраска рёбер невозможна.

Иначе выведите «YES» (без кавычек). В $$$i$$$-й из $$$m$$$ следующих строк выведите $$$1$$$, если $$$i$$$-й муравей будет использовать первую пару, и $$$2$$$ иначе. Если существует несколько решений, выведите любое из них.

Примеры
Входные данные
6
1 2
3 1
4 1
5 2
6 2
3
2 6 3 4
1 6 6 5
1 4 5 2
Выходные данные
YES
2
1
2
Входные данные
5
1 2
1 3
1 4
1 5
2
2 3 4 5
3 4 5 2
Выходные данные
NO
Примечание

В примере второе и третье ребро следует покрасить в первый цвет, первое и пятое — во второй цвет, а четвёртое — в третий цвет.