Coin Exchange

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.

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.

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.