You are given a graph containing n vertices and m edges. Vertices are numbered from 0 to n-1. Initially, vertex i belongs to group i. We define a group A is connected to group B if and only if there exists at least an edge that connects the two vertices which belong to A and B respectively.

Now we will do q operations on this graph. The i-th operation is represented by an integer .

In i-th operation, if there are no vertices belong to group , nothing happens. Otherwise, for all vertices belong to a group which is connected to , those vertices will belong to group  after this operation.

Now you are also given the q operations. Please answer each vertex belongs to which group after all operations.

输入描述:

The first line contains one integer t () --- the number of test cases.

The first line of each test contains two positive integers n and m (, ) --- the number of vertices and edges in the given graph.

The following are m lines. Each of them contains two integers x and y, indicating there is an edge between vertex x and vertex y (, there are no duplicate edges in the same test)

The following line contains one integer q () -- the number of operations in this test. Then there is one more line contains q integers  ().

The sum of n across the test cases doesn't exceed .

The sum of m across the test cases doesn't exceed .

And the sum of q across the test cases doesn't exceed .

输出描述:

For each test, output one line contains n integers --- the i-th integer of them representing the group that the vertex i-1 belongs to.

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

0 0 0 0
2 2 2 2
0 0 3 3
0 1 2 3
0 0 0 0 0

Take the first test for example:

Initially, the four vertex is belong to 0, 1, 2, 3 respectively.

After the first operation, the four vertex is belong to 0, 0, 2, 3 respectively.

After the second operation, because there is no vertex belong to 1 now. The four vertex is still belong to 0, 0, 2, 3 respectively.

After the third operation, the four vertex is belong to 0, 0, 3, 3 respectively.

After the last operation, the four vertex is belong to 0, 0, 0, 0 respectively.