CF1007D Ants

有一棵包含 $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$），表示第 $i$ 只蚂蚁最喜欢的两对顶点对 $(a_i, b_i)$ 和 $(c_i, d_i)$。

如果无法实现所需的染色方式，输出 “NO”。 否则，输出 “YES”。接下来输出 $m$ 行，第 $i$ 行输出 $1$ 表示第 $i$ 只蚂蚁选择第一对顶点对，输出 $2$ 表示选择第二对顶点对。如果有多种方案，输出任意一种均可。

在样例中，第二条和第三条边应染成第一种颜色，第一条和第五条边应染成第二种颜色，第四条边应染成第三种颜色。 由 ChatGPT 4.1 翻译