시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 140 | 39 | 29 | 24.786% |
Proper k-coloring of undirected graph G(V, E) is a mapping c : V → {1, 2, 3, . . . , k} such that for each edge (u, v) ∈ E, we have cu ≠ cv.
Undirected graph is k-colorable if a proper k-coloring exists for it.
Chromatic number of a graph is the smallest k such that the graph is k-colorable.
Tree is a simple acyclic undirected graph.
Alice has an undirected graph with chromatic number k, and Bob has a tree on k vertices. Bob wants to find k different vertices p1, p2, p3, . . . , pk in Alice’s graph such that for each edge (u, v) in Bob’s tree, there exists an edge (pu, pv) in Alice’s graph. Help him.
The first line contains a single integer T (1 ≤ T ≤ 106), the number of test cases to solve. Description of T testcases follows. Each testcase is described as follows.
The first line contains three integers n, m, and k (1 ≤ n, k ≤ 106, 0 ≤ m ≤ 106), the number of vertices and edges of Alice’s graph and its chromatic number, respectively.
Each of the next m lines contains a pair of integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) describing an edge of Alice’s graph. It is guaranteed that there are no multiple edges and that Alice’s graph has chromatic number exactly equal to k.
Each of the next k − 1 lines contains a pair of integers pi and qi (1 ≤ pi, qi ≤ k, pi ≠ qi) describing an edge in Bob’s tree. It is guaranteed that the given set of edges forms a tree.
It is guaranteed that the sum of n in all test cases, as well as the sum of m in all test cases, does not exceed 106.
For each testcase, output the answer in the following format.
If it is impossible to find the required k vertices in Alice’s graph, print “No”.
Otherwise, print “Yes” in the first line. In the second line, print k different integers pi (1 ≤ pi ≤ n): the numbers of vertices in Alice’s graph corresponding to the respective vertices of Bob’s tree. If there are several possible answers, print any one of them.
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
Yes 3 2 1 Yes 4 1 2 3 Yes 5 4 3