# OPTM - Optimal Marks

## 题意翻译

给你一个无向图G（V，E）。 每个顶点都有一个int范围内的整数的标记。 不同的顶点可能有相同的标记。
对于边（u，v），我们定义Cost（u，v）= mark [u] xor mark [v]。
现在我们知道某些节点的标记了。你需要确定其他节点的标记，以使边的总成本尽可能小。
感谢@耀晨_wcx 提供的翻译

## 题目描述

You are given an undirected graph G(V, E). Each vertex has a mark which is an integer from the range \[0..2 $ ^{31} $ – 1\]. Different vertexes may have the same mark.
For an edge (u, v), we define Cost(u, v) = mark\[u\] xor mark\[v\].
Now we know the marks of some certain nodes. You have to determine the marks of other nodes so that the total cost of edges is as small as possible.

## 输入输出格式

### 输入格式

The first line of the input data contains integer **T** (1 ≤ **T** ≤ 10) - the number of testcases. Then the descriptions of T testcases follow.
First line of each testcase contains 2 integers **N** and **M** (0 < **N** <= 500, 0 <= **M** <= 3000). **N** is the number of vertexes and **M** is the number of edges. Then **M** lines describing edges follow, each of them contains two integers u, v representing an edge connecting u and v.
Then an integer **K**, representing the number of nodes whose mark is known. The next **K** lines contain 2 integers u and p each, meaning that node u has a mark p. It’s guaranteed that nodes won’t duplicate in this part.

### 输出格式

For each testcase you should print **N** lines integer the output. The **K**th line contains an integer number representing the mark of node **K**. If there are several solutions, you have to output the one which minimize the sum of marks. If there are several solutions, just output any of them.

## 输入输出样例

### 输入样例 #1

```
1
3 2
1 2
2 3
2
1 5
3 100
```

### 输出样例 #1

```
5
4
100
```