도미노

정신없는 뻐꾸기 찰리(Crazy Cuckoo Charlie)는 워털루 기록집(Book of Waterloo Records)에 이름을 올리고 싶어 하는 컴퓨터 과학과 학생입니다. 안타깝게도 그에게는 특별한 재능이 없습니다. 대신 아주 많은 시간과, 아주 많은 도미노가 있습니다. 그는 도미노를 한 줄로 최대한 길게 이어 붙이는 "워털루에서 가장 긴 도미노 사슬" 기록에 도전하려고 합니다.

도미노는 두 개의 반쪽으로 이루어져 있고, 각 반쪽에는 점의 개수가 적혀 있습니다. 기록을 세우려면 찰리는 모든 도미노를 한 줄로 끝과 끝을 맞대어 배치해야 합니다. 그런데 규칙이 하나 더 있습니다. 이웃한 두 도미노가 맞닿는 반쪽에 적힌 점의 개수가 서로 같아야 합니다(위 그림 참고).

찰리는 가지고 있는 모든 도미노를 사용해 사슬을 만들고 싶습니다. 하지만 이 규칙 때문에 가진 도미노만으로는 사슬을 완성하지 못할 수도 있습니다(예를 들어 1 2와 4 5만 있으면 이을 수 없습니다). 그래서 그는 도미노를 추가로 사려고 합니다. 물론 피자와 음료수처럼 더 중요한 데 돈을 쓰기 위해, 최대한 적은 개수의 도미노만 사고 싶어 합니다.

찰리가 가진 모든 도미노를 하나의 사슬로 이어 붙이기 위해 추가로 사야 하는 도미노의 최소 개수를 구해 주세요.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 하나의 도미노 모음을 나타냅니다. 첫 번째 줄에는 테스트 케이스의 총 개수를 나타내는 정수 $N$이 주어집니다. 각 테스트 케이스의 첫 줄에는 찰리가 가진 도미노의 개수를 나타내는 정수 $K$가 주어집니다($1 < K < 10,000$). 이어지는 $K$개의 줄에는 각 도미노가 A B 형태로 주어지며, $A$와 $B$는 도미노의 두 반쪽에 적힌 점의 개수를 나타내는 양의 정수입니다($0 < A < B < 50,000$). 도미노는 뒤집어서 사용할 수 있다는 점을 잊지 마세요.

각 테스트 케이스마다, 찰리가 가진 모든 도미노를 하나의 사슬로 이어 붙일 수 있도록 추가로 사야 하는 도미노의 최소 개수 $X$를 한 줄에 하나씩 출력합니다.

이번 주에 배운 것처럼, 많은 문제를 그래프로 모델링할 수 있습니다. 이 문제도 그중 하나입니다.

참고로 오일러 경로(Euler path)는 그래프의 모든 간선을 지나는 경로입니다(해밀턴 경로와는 전혀 다릅니다). 그래프에 오일러 경로가 존재할 필요충분조건은 다음 두 가지가 모두 성립하는 것입니다.

1. 그래프가 연결되어 있다(어디서든 어디로든 이동할 수 있다).
2. 차수가 홀수인 정점(정점에 닿는 간선의 개수가 홀수인 정점)의 개수가 2개 이하이다.