A11930 | 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.

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.