시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
7 초 256 MB 466 121 62 30.542%

문제

V의 집합과 간선 E의 집합으로 이루어진 양방향 그래프 G = ( V, E )가 주어진다. 이 그래프는 연결 그래프이다. 즉, 모든 정점쌍 간에 적어도 하나 이상의 경로가 존재한다. 각각의 정점들은 검정색 또는 흰색이다. 동전은 정점들 위에 하나씩 놓여 있는데 이 동전도 검정색 또는 흰색이다. 이 그래프에서 '동전 교환' 연산을 통해 인접한 정점 위에 있는 동전 2개의 위치를 서로 맞바꿀 수 있다. 아래 그림을 보면 이해 할 수 있을 것이다. (그림 1에서 네모의 색은 동전의 색깔이다.)

그림 1. '동전 교환' 연산의 예 (2 <> 5, 5 <> 6, 1 <> 5)

우리가 구하고자 하는 것은 모든 검정색 동전을 검정색 정점 위로, 모든 흰색 동전을 흰색 정점 위로 올리기 위해 필요한 '동전 교환' 연산의 최소 횟수이다.

입력

입력의 첫줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫줄에는 정수 n과 m (1 ≤ n ≤ 500, n-1 ≤ m ≤ n(n-1)/2 )이 주어진다. 여기서 n은 정점의 갯수, m은 간선의 갯수를 나타낸다. 정점은 1 ~ n의 번호를 가진다. n, m의 다음줄부터 m 줄에 걸쳐서 인접한 두 정점 x, y (1 ≤ x < y ≤ n)이 주어진다. 그 다음 줄에는 0 또는 1의 값을 가지는 n개의 정수가 주어진다. 여기서 i (1 ≤ i ≤ n)번째 정수는 정점 i의 색깔이다. 0은 검정색 1은 흰색이다. 그 다음 줄에도 0 또는 1의 값을 가지는 n개의 정수가 주어지고 여기서 i (1 ≤ i ≤ n)번째 정수는 정점 i위에 있는 동전의 색깔을 의미한다.

출력

한 테스트케이스당 한 줄에 걸쳐 모든 동전과 정점의 색깔을 일치시키기 위해 필요한 최소 '동전 교환' 연산의 횟수를 출력하라.

예제 입력

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

힌트