Ants

题意翻译

有一棵树有 $n$ 个顶点。还有 $m$ 只蚂蚁住在上面。每只蚂蚁都有自己的颜色。第 $i$ 只蚂蚁有两个最喜欢的顶点对：($a_i, b_i)$ 和 $(c_i, d_i)$。你需要知道是否可以用 $m$ 种颜色绘制树的边，以便每个蚂蚁能在其最喜欢的一对顶点对之间行走且这条边的颜色与这只蚂蚁相同；如果可能，你需要输出每个蚂蚁行走的顶点对。 如果不可能的话，输出 `NO`。 否则输出 `YES` 并输出 $m$ 行。在第 $i$ 行，如果第 $i$ 只蚂蚁将使用第一个顶点对，则输出 $1$，否则输出 $2$。

题目描述

There is a tree with $ n $ vertices. There are also $ m $ ants living on it. Each ant has its own color. The $ i $ -th ant has two favorite pairs of vertices: ( $ a_i, b_i $ ) and ( $ c_i, d_i $ ). You need to tell if it is possible to paint the edges of the tree in $ m $ colors so that every ant will be able to walk between vertices from one of its favorite pairs using only edges of his color; if it is possible, you need to print which pair every ant should use.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 2 \leq n \leq 10^5 $ ) — the number of vertices. Each of the next $ n-1 $ lines contains two integers $ u_i $ and $ v_i $ ( $ 1 \leq u_i, v_i \leq n $ ), meaning that there is an edge between vertices $ u_i $ and $ v_i $ . The next line contains a single integer $ m $ ( $ 1 \leq m \leq 10^4 $ ) — the number of ants. Each of the next $ m $ lines contains four integers $ a_i $ , $ b_i $ , $ c_i $ , and $ d_i $ ( $ 1 \leq a_i, b_i, c_i, d_i \leq n $ , $ a_i \neq b_i, c_i \neq d_i $ ), meaning that pairs ( $ a_i $ , $ b_i $ ) and ( $ c_i $ , $ d_i $ ) are favorite for the $ i $ -th ant.

输出格式

Print "NO" (without quotes) if the wanted painting is impossible. Otherwise, print "YES" (without quotes). Print $ m $ lines. On the $ i $ -th line, print $ 1 $ if the $ i $ -th ant will use the first pair and $ 2 $ otherwise. If there are multiple answers, print any.

输入输出样例

输入样例 #1

6
1 2
3 1
4 1
5 2
6 2
3
2 6 3 4
1 6 6 5
1 4 5 2

输出样例 #1

YES
2
1
2

输入样例 #2

5
1 2
1 3
1 4
1 5
2
2 3 4 5
3 4 5 2

输出样例 #2

NO

说明

In the sample, the second and the third edge should be painted in the first color, the first and the fifth should be painted in the second color, and the fourth should be painted in the third color.