문제
대한민국은 N개의 도시와 M개의 양방향 도로로 나타낼 수 있다.
대한민국의 대통령이 된 장태환은 지역 순회를 하고자 한다.
지역 순회를 하는 장태환은 어떤 도시에서 출발하여 도로를 따라 이동한 뒤 출발했던 도시로 도착한다.
지역 편애 논란이 생기면 안 되기 때문에, 어떤 도시도 두 번 방문할 수는 없다.(출발은 방문에서 제외하지만, 도착은 방문에 포함한다.)
또한, 지역 순회에서 할 행사들의 계획을 지키기 위해서는, 방문하는 도시의 수는 홀수가 되어야 한다.
이 조건을 따라 장태환이 전국 순회를 할 때, 장태환이 방문할 가능성이 있는 도시의 수를 구하여라.
입력
첫째 줄에 테스트케이스의 수 T가 주어진다.(T<=100)
테스트케이스의 첫째 줄에 N,M이 주어진다(0<=N.M<=100000)
다음 M줄에 도로가 잇는 두 도시 a,b가 주어진다.
출력
총 T줄에 걸쳐 각 테스트케이스마다 장태환이 방문할 가능성이 있는 도시의 수를 출력하여라.
예제
1
7 7
1 5
3 5
3 7
1 7
6 7
4 7
4 6
3
출처
SEERC 2008
로그인해야 코드를 작성할 수 있어요.