Problem Setter: Maruf Ahmed Rahad

Intake 35, Department of CSE

BUBT is a famous university. It’s CSE department is very advanced because they produce good programmers nowadays. They arrange a programming contest in every semester. But this time the programmers don’t want to participate in the contest by risking their lives. That’s why Dipu sir set some students to guard the streets (which are outside of  BUBT) for the programmers’ safety. There are lots of stations and streets (bi-directional). The students have to guard all the stations and streets. A student can guard the streets and stations adjacent to it. But the students are not well behaved. If a street is guarded by multiple students they start fighting. So Dipu sir asked Zabir to write a program that finds the minimum number of students to guard all the stations and roads. Since Zabir is not a good programmer he needs your help.

Input Format

The first line of the input contains a single integer T (T <= 100), indicating the number of test cases. Each test case begins with 2 integers n (1 ≤ n ≤ 250) and m (0 ≤ m ≤ 10000). Here, n is the number of stations and m is the number of streets. Each of the next m lines contains 2 integers a and b denoting that there is a street between the stations a and b. All the stations are numbered from 0 to n−1.

Output Format

For each test case output in a single line an integer X denoting the minimum number of guards needed to guard all the stations and streets. If not possible print -1.

Samples