无向图 $G(V, E)$ 的真 $k$-着色（proper $k$-coloring）是一个映射 $c : V \to \{1, 2, 3, \dots, k\}$，使得对于每一条边 $(u, v) \in E$，都有 $c_u \neq c_v$。 如果一个无向图存在真 $k$-着色，则称该图是 $k$-可着色的。 图的色数（chromatic number）是使得图 $k$-可着色的最小 $k$ 值。 树是一个简单的无环无向图。

Alice 有一个色数为 $k$ 的无向图，Bob 有一个包含 $k$ 个顶点的树。Bob 想要在 Alice 的图中找到 $k$ 个不同的顶点 $p_1, p_2, p_3, \dots, p_k$，使得对于 Bob 树中的每一条边 $(u, v)$，在 Alice 的图中都存在一条边 $(p_u, p_v)$。请帮助他。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^6$)，表示测试用例的数量。接下来是 $T$ 个测试用例的描述。每个测试用例描述如下：

第一行包含三个整数 $n, m$ 和 $k$ ($1 \le n, k \le 10^6, 0 \le m \le 10^6$)，分别表示 Alice 图的顶点数、边数及其色数。

接下来的 $m$ 行，每行包含一对整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，描述 Alice 图中的一条边。保证图中没有重边，且 Alice 图的色数恰好等于 $k$。

接下来的 $k - 1$ 行，每行包含一对整数 $p_i$ 和 $q_i$ ($1 \le p_i, q_i \le k, p_i \neq q_i$)，描述 Bob 树中的一条边。保证给定的边集构成一棵树。

保证所有测试用例中 $n$ 的总和以及 $m$ 的总和均不超过 $10^6$。

输出格式

对于每个测试用例，按以下格式输出答案：

如果无法在 Alice 的图中找到所需的 $k$ 个顶点，输出 “No”。

否则，第一行输出 “Yes”。第二行输出 $k$ 个不同的整数 $p_i$ ($1 \le p_i \le n$)：表示对应于 Bob 树中各个顶点的 Alice 图中的顶点编号。如果存在多种可能的答案，输出其中任意一个即可。

样例

样例输入 1

3
6 6 3
1 2
2 3
3 1
1 4
2 5
3 6
1 2
2 3
4 6 4
1 2
1 3
1 4
2 3
2 4
3 4
1 2
1 3
1 4
5 4 3
1 2
3 4
4 5
5 3
1 2
2 3

样例输出 1

Yes
3 2 1
Yes
4 1 2 3
Yes
5 4 3