CF923F Public Service

Bob 的国家有 $N$ 个城市，这些城市通过公路相连。部分城市对之间还通过公共交通工具相连。有两家竞争的交通公司——Boblines 运营公交车，Bobrail 运营火车。从 $A$ 城到 $B$ 城时，乘客总是先选择交通方式（公交或火车），然后开始旅程。对于每一对城市，存在恰好两种不重复经过城市的出行方式——一种仅使用公交线路，另一种仅使用火车线路。此外，没有任何一对城市同时通过公交和火车直接相连。 你获得了两家公司的网络规划图。不幸的是，两家公司对同一城市使用了不同的编号方式。具体来说，公交公司用 $1$ 到 $N$ 编号城市，而火车公司用 $N+1$ 到 $2N$ 编号城市。请你找出一种可能的编号映射方案，使得没有任何一对城市同时通过公交和火车直接相连。注意，这个映射需要将不同的城市映射到不同的城市。

第一行包含一个整数 $N$（$2 \leq N \leq 10000$），表示城市数量。 接下来 $N-1$ 行，每行两个整数 $u$ 和 $v$（$1 \leq u,v \leq N$），表示城市 $u$ 和 $v$ 之间有一条公交线路。 再接下来 $N-1$ 行，每行两个整数 $u$ 和 $v$（$N+1 \leq u,v \leq 2N$），表示城市 $u$ 和 $v$ 之间有一条火车线路。

如果无解，输出一行 "No"。 如果有解，输出两行。第一行输出 "Yes"。第二行输出 $N$ 个整数 $P_1, P_2, ..., P_N$（$N+1 \leq P_i \leq 2N$），表示编号映射方案。更具体地说，对于 $i \neq j$，应有 $P_i \neq P_j$，并且对于每一条公交线路 $(i, j)$，火车线路中不存在 $(P_i, P_j)$ 这条直接线路。 如果有多组解，输出任意一组均可。

第一个样例（红色为公交线路，蓝色为火车线路）：  由 ChatGPT 4.1 翻译