← 返回题目列表

Codeforces · 1007/D

D. 蚂蚁

中文机器翻译题面 查看原题

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$$$).你需要判断是否可以用 $$$m$$$ 颜色绘制树的边缘,以便每只蚂蚁都能够仅使用其颜色的边缘在它最喜欢的一对的顶点之间行走; 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.

接下来的 $$$n-1$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$),这意味着顶点 $$$u_i$$$ 和 $$$v_i$$$ 之间有一条边。

The next line contains a single integer $$$m$$$ ($$$1 \leq m \leq 10^4$$$) — the number of ants.

接下来的 $$$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$$$), 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).打印 $$$m$$$ 行。 On the $$$i$$$-th line, print $$$1$$$ if the $$$i$$$-th ant will use the first pair and $$$2$$$ otherwise.如果有多个答案,请打印其中一个。

示例

输入 #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.