등산로

대재앙 이후, 온갖 자연재해가 지구를 휩쓸고 지나간 뒤 살아남은 인류 문명은 재건을 시작했다. 그 여파로 독특한 관광 산업이 생겨났는데, 사람들이 재앙 이전 대도시의 잔해를 탐험하며 지난 시대의 기념품을 찾아다니는 것이다. 당신은 한때 로스앤젤레스였던 도시의 관광청에서 일하며, 관광객이 탐험에 이용하는 등산로를 정비하는 일을 맡았다.

각 등산로는 두 명소를 잇는다. 관광청은 등산로로 서로 연결되어 있기를 바라는 명소들의 목록을 가지고 있다. 최근 목록에 추가된 명소 중에는 아직 등산로 망에 연결되지 않은 것도 있을 수 있다. 당신이 할 일은, 모든 명소 쌍이 일련의 등산로를 통해 서로 오갈 수 있도록 가장 적은 수의 등산로를 추가하는 방법을 찾는 것이다.

등산로 자체도 명소만큼이나 흥미롭기 때문에 관광청은 또 하나의 조건을 걸었다. 어느 명소에서 출발하든, 각 등산로를 정확히 한 번씩만 지나면서 모든 명소를 한 번 이상 방문하고 출발한 명소로 되돌아올 수 있어야 한다. 이는 모든 명소가 짝수 개의 등산로와 연결되어 있을 때에만 가능하다. 이제 필요한 것은, 이 조건을 만족시키기 위해 추가해야 하는 등산로의 최소 개수를 구하는 프로그램뿐이다.

명소는 1번부터 L번까지 번호가 매겨져 있다.

첫 번째 줄에는 데이터 집합의 개수 K가 주어진다. 그 뒤로 K개의 데이터 집합이 이어지며, 각 데이터 집합의 형식은 다음과 같다.

첫 줄에 두 정수 L과 T가 주어진다 ($2 \le L \le 1000$, $1 \le T \le 5000$). L은 등록된 명소의 수, T는 이미 존재하는 등산로의 수이다. 명소는 1번부터 L번까지 번호가 매겨져 있다. 이어지는 T개의 줄에는 각각 두 정수 A와 B가 주어지며 ($1 \le A, B \le L$), 명소 A와 B를 잇는 등산로가 존재함을 뜻한다. 한 명소를 자기 자신과 잇는 등산로는 없으며, 두 명소를 잇는 등산로는 많아야 하나임을 가정해도 좋다. 단, 새 등산로를 추가할 때는 이미 등산로로 연결된 두 명소 사이에도 등산로를 추가할 수 있다.

각 데이터 집합에 대해, 한 줄에 "Data Set x:"를 출력한다. 여기서 x는 데이터 집합의 번호이다. 다음 줄에는 조건을 만족시키기 위해 추가해야 하는 등산로의 최소 개수를 출력한다. 각 데이터 집합 뒤에는 빈 줄을 하나 출력한다.