#1373 한붓그리기 가능하게 고치기

67  1 s   128 MB  

Description

연결된 멀티그래프가 주어진다. 멀티그래프란, 임의의 두 정점 사이에 간선이 하나 이상 있을 수 있는 그래프이다.

이 멀티그래프가 한붓그리기가 가능하도록 간선을 추가한다면, 최소 몇 개의 간선을 추가해야 하는가?

Input

입력은 여러 개의 테스트 케이스로 구성된다. 첫 행에는 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 행에는 두 정수 V, E가 주어진다. V는 정점의 수로 100 이하이고, E는 간선의 수로 10000 이하이다.

다음 E 개의 행에 걸쳐 간선의 양 끝 인덱스가 공백으로 구분되어 주어진다. 각 인덱스는 0부터 센다.

Output

각 테스트 케이스에 대해 한 행에 하나씩 답안을 출력한다.

Sample Input

Sample Output

2
3 2
0 1
1 2
4 3
0 1
1 2
1 3
0
1