CF1007D.Ants

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.

有一棵包含 $n$ 个顶点的树。树上还生活着 $m$ 只蚂蚁。每只蚂蚁都有其专属的颜色。第 $i$ 只蚂蚁有两个偏爱的顶点对：$(a_i, b_i)$ 和 $(c_i, d_i)$。你需要判断：是否可以将树的边染成 $m$ 种颜色，使得每只蚂蚁都能仅通过与其自身颜色相同的边，在其某个偏爱的顶点对之间通行；若可行，则还需输出每只蚂蚁应选择哪一个顶点对。

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.

第一行包含一个整数 $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$），表示第 $i$ 只蚂蚁的两个喜爱点对为 $(a_i, b_i)$ 和 $(c_i, d_i)$。

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.

如果目标涂色方案无法实现，则输出 "NO"（不带引号）。

否则，输出 "YES"（不带引号），并输出 $m$ 行。在第 $i$ 行中，若第 $i$ 只蚂蚁使用第一对颜料，则输出 $1$，否则输出 $2$。若存在多种可行方案，输出任意一种即可。

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.

在样例中，第二条和第三条边应涂上第一种颜色，第一条和第五条边应涂上第二种颜色，第四条边应涂上第三种颜色。