동전 교환

정점 집합 $V$와 간선 집합 $E$로 이루어진 무방향 그래프 $G = (V, E)$가 주어진다. 이 그래프는 연결 그래프여서 모든 정점 쌍 사이에 적어도 하나의 경로가 있다. 각 정점은 검은색이거나 흰색이고, 모든 정점 위에는 동전이 하나씩 놓여 있다. 동전도 검은색이거나 흰색이다.

'동전 교환' 연산은 간선으로 이어진 두 정점 위에 놓인 동전 두 개의 자리를 서로 맞바꾼다.

그림 1. '동전 교환' 연산의 예 (2와 5, 5와 6, 1과 5). 네모의 색은 동전의 색이다.

모든 검은색 동전을 검은색 정점 위로, 모든 흰색 동전을 흰색 정점 위로 올리려고 한다. 이때 필요한 '동전 교환' 연산의 최소 횟수를 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 정점의 개수 $n$과 간선의 개수 $m$이 주어진다 ($1 \le n \le 500$, $n-1 \le m \le n(n-1)/2$). 정점 번호는 1부터 $n$까지다. 이어지는 $m$개의 줄에는 간선으로 이어진 두 정점 $x$, $y$가 주어진다 ($1 \le x < y \le n$). 그 다음 줄에는 0 또는 1인 정수 $n$개가 주어지고, $i$번째 정수는 정점 $i$의 색이다. 0은 검은색, 1은 흰색이다. 마지막 줄에도 0 또는 1인 정수 $n$개가 주어지고, $i$번째 정수는 정점 $i$ 위에 놓인 동전의 색이다.

모든 동전과 정점의 색을 일치시킬 수 있는 입력만 주어진다.

각 테스트 케이스마다 모든 동전과 정점의 색을 일치시키는 데 필요한 '동전 교환' 연산의 최소 횟수를 한 줄에 하나씩 출력한다.