Coin Exchange

Time limit8sMemory limit256 MB

Summary

Find the fewest swaps along graph edges that place every black coin on a black vertex and every white coin on a white vertex.

Level: Medium7 of 10
Topics: Shortest path, Graph, Dynamic programming
Solved: No attempts yet

Problem

You are given an undirected graph $G = (V, E)$ with vertex set $V$ and edge set $E$ . The graph is connected, so at least one path runs between every pair of vertices. Each vertex is black or white, and every vertex holds exactly one coin. Each coin is black or white.

A coin exchange takes two vertices joined by an edge and swaps the two coins sitting on them.

Figure 1. Examples of a coin exchange (2 with 5, 5 with 6, 1 with 5). The color of a square is the color of a coin.

You want every black coin to end up on a black vertex and every white coin on a white vertex. Find the minimum number of coin exchanges that achieves this.

Input

The first line contains the number of test cases $T$ .

The first line of each test case contains the number of vertices $n$ and the number of edges $m$ ( $1 \le n \le 500$ , $n-1 \le m \le n(n-1)/2$ ). Vertices are numbered 1 to $n$ . Each of the next $m$ lines contains two vertices $x$ and $y$ joined by an edge ( $1 \le x < y \le n$ ). The next line contains $n$ integers, each 0 or 1, where the $i$ -th integer is the color of vertex $i$ . 0 is black and 1 is white. The last line contains $n$ integers, each 0 or 1, where the $i$ -th integer is the color of the coin sitting on vertex $i$ .

Only inputs where every coin can be matched to a vertex of the same color are given.

Output

For each test case, print on its own line the minimum number of coin exchanges needed to put every coin on a vertex of its own color.

Examples3

Example 1

Input

3
4 4
1 2
1 3
2 4
3 4
0 1 1 0
0 1 0 1
6 7
1 2
1 5
1 4
2 3
2 5
4 5
5 6
1 1 0 0 0 0
0 0 0 0 1 1
6 5
1 2
2 3
3 4
4 5
5 6
1 0 1 1 0 0
0 0 1 1 0 1

Expected output

1
3
5

Example 2
Input
```
2
1 0
0
0
1 0
1
1
```
Expected output
```
0
0
```

Example 3

Input

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

Expected output