동전 교환

시간 제한8초메모리 제한256 MB

요약

그래프 간선을 따라 동전을 교환해 모든 동전을 같은 색 정점에 옮기는 최소 횟수를 구합니다.

난이도: 보통10점 중 7점
유형: 최단 경로, 그래프, 동적 계획법
정답자: 아직 제출이 없습니다

문제

정점 집합 $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$ 위에 놓인 동전의 색이다.

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

출력

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

예제3

예제 1

입력

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

예상 출력

1
3
5

예제 2
입력
```
2
1 0
0
0
1 0
1
1
```
예상 출력
```
0
0
```

예제 3

입력

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

예상 출력