행운의 도시

John은 South Eastern European Regional 대회를 위해 최근 루마니아에 도착했다. John은 루마니아에 처음 와 보기 때문에, 주최 측은 그를 위한 관광 투어를 준비했다. 이 투어는 여러 루마니아 도시를 포함하며, 어떤 도시도 두 번 이상 방문하지 않는다. John은 한 도시에서 출발해 안내된 경로를 따라 다른 도시들을 방문하고, 투어가 끝나면 출발한 도시로 돌아온다.

이 나라에는 1번부터 $N$번까지 번호가 매겨진 도시 $N$개와 양방향 도로 $M$개가 있다. 각 도로는 서로 다른 두 도시를 잇는다. John의 관광 투어란 도시들의 수열 $c_1, c_2, \dots, c_n$ 으로, 모든 $c_i$ 가 서로 다르고, $i = 1, 2, \dots, n-1$ 에 대해 $c_i$ 와 $c_{i+1}$ 이 도로로 연결되어 있으며, $c_n$ 과 $c_1$ 도 도로로 연결되어 있는 것을 말한다.

John은 홀수를 좋아하는 사람이라 홀수 개의 도시를 방문하고 싶어 한다. 주최 측은 방문하는 도시의 수가 홀수인 가능한 모든 투어의 계획을 그려 두었으며, 그러한 투어만 고려한다.

각 도시의 주민들은 John이 자기 도시를 방문해 주기를 바란다. 어떤 도시를 지나가는, 방문 도시 수가 홀수인 투어가 하나라도 존재하면 그 도시를 행운의 도시라고 부른다. 루마니아에 있는 행운의 도시의 수를 구하여라.

입력의 첫 줄에는 정수 $T$ — 테스트 케이스의 수가 주어진다. 각 테스트 케이스는 공백 하나로 구분된 두 정수 $N$ 과 $M$ 이 있는 줄로 시작한다. 이어지는 $M$ 개의 줄에는 각각 공백 하나로 구분된 두 정수 $a_i$ 와 $b_i$ 가 주어지며, 이는 $i$ 번째 도로가 잇는 두 도시의 번호이다.

$T$ 개의 줄에 각 테스트 케이스에 대한 답을 순서대로 출력한다.

• $1 \le T \le 77$
• $0 \le N, M \le 10^5$
• $1 \le a_i < b_i \le N$