5D.环线规划（route）

C 国由 $n$ 个城市组成，编号为 $1$ 到 $n$。这些城市由 $n-1$ 条双向道路互相连接，且任意两个城市都能通过这些道路互相到达。

现在 C 国的规划中心决定在这些道路上修建一条快速交通环线，这条环线是一条经过所有城市的 闭合 路线，且恰好经过每条道路的两个方向各一次。一条环线可以表示为一个长度为 $2n-1$ 的城市序列 $p_0,p_1,\ldots,p_{2n-2}$，满足：

• $p_0=p_{2n-2}$；
• 对于任意 $1\le i\le 2n-2$，城市 $p_{i-1}$ 与 $p_{i}$ 之间都有道路连接；
• 每条道路的两个方向都在序列中恰好出现一次。

注意，一个城市可能在环线中出现多次。

接下来，环线上将会开设两班列车，分别按照 $p_0\to p_1\to \cdots\to p_{2n-2}\to \cdots$ 与 $p_{2n-2}\to p_{2n-3}\to \cdots\to p_0\to \cdots$ 的顺序循环运行。

同时，市政部向规划中心提出了 $q$ 个要求，每个要求的形式如下：

• 给定两个城市 $x,y$，需要保证，某乘客从城市 $x$ 可以乘坐列车到达城市 $y$，并且在乘坐过程中不会重复经过同一个城市。注意，如果城市 $x$ 在环线中出现多次，乘客只需要选择合适的一次出现乘坐列车。

这对规划中心的专家们来说实在太难了，所以他们找到了你，算法大师小 F，帮助他们设计一个符合全部要求的环线，或者指出这样的环线实际上不存在。

从文件 route.in 中读入数据。

本题包含多组测试数据。输入的第一行包含两个正整数 $c,t$，分别表示测试点编号以及测试数据组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

• 第一行包含两个正整数 $n,q$，分别表示 C 国的城市个数和市政部的要求个数；
• 接下来 $n-1$ 行，第 $i$ 行两个正整数 $u_i,v_i$，表示存在一条连接城市 $u_i$ 和城市 $v_i$ 的双向道路。保证任意两个城市都能通过这些道路互相到达。
• 接下来 $q$ 行，第 $i$ 行两个正整数 $x_i,y_i$，表示一个要求。

输出到文件 route.out。

对于每组测试数据：

• 如果不存在符合全部要求的环路，输出一行 No；
• 否则，在输出的第一行输出 Yes，在第二行输出 $2n-1$ 个正整数 $p_0,p_1,\ldots,p_{2n-1}$，表示你所规划的环路。

0 3
2 1
1 2
1 2
4 3
1 2
1 3
1 4
2 3
2 4
3 4
5 3
1 2
1 3
1 4
1 5
2 3
2 4
2 5

Yes
1 2 1
Yes
1 2 1 3 1 4 1
No

对于第一组测试数据，只有一条道路，环线可以为 $1\to2\to1$。

对于第二组测试数据，环线可以为 $1\to2\to1\to3\to1\to4\to1$。任意两个叶子城市之间都可以选择合适方向乘车，并且途中不会重复经过城市。

对于第三组测试数据，三个要求分别迫使通向城市 $2$ 的道路在城市 $1$ 处与通向城市 $3,4,5$ 的道路相邻。然而在环线经过城市 $1$ 时，一条道路在局部环形顺序中只能与两条道路相邻，因此不存在满足全部要求的环线。

该样例满足测试点 $1,2$ 的限制条件。

该样例满足测试点 $4,5$ 的限制条件。

该样例满足测试点 $6$ 的限制条件。

该样例满足测试点 $7\sim 9$ 的限制条件。

该样例满足测试点 $12$ 的限制条件。

该样例满足测试点 $15$ 的限制条件。

该样例满足测试点 $16,17$ 的限制条件。

该样例满足测试点 $18\sim 20$ 的限制条件。

该样例满足测试点 $21\sim 23$ 的限制条件。

设 $\sum n$ 表示单测试点内所有测试数据中 $n$ 的和，$\sum q$ 表示单测试点内所有测试数据中 $q$ 的和。

对于全部测试数据，保证：

• $1\le t \le 10^4$；
• $2\le n\le 3\cdot 10^5$，$\sum n\le 10^6$；
• $1\le q\le \min\left(5\cdot 10^5,\frac{n(n-1)}{2}\right)$，$\sum q\le 10^6$；
• 对于任意 $1\le i\le n-1$，$1\le u_i<v_i\le n$，且任意两个城市均可通过道路互相到达；
• 对于任意 $1\le i\le q$，$1\le x_i<y_i\le n$，且 $(x_1,y_1),(x_2,y_2) ,\ldots,(x_q,y_q)$ 互不相同。

• 特殊性质 A：对于任意 $1\le i\le n-1$，$u_i=i$，$v_i=i+1$；
• 特殊性质 B：对于任意 $1\le i\le n-1$，$u_i=1$；
• 特殊性质 C：每个城市至多与 $3$ 条道路相连。