ADACROW - Ada and Scarecrow


As you might already know, Ada the Ladybug is a farmer. She has multiple farmhouses and some fields which always connect two adjacent farmhouses. She plans to buy some scarecrows to scare crows!

A scarecrow placed on a farmhouse scares all crows from all adjacent fields. A crow on a field can be disastrous, so Ada has to arrange the scarecrows in such way that they cover all the fields. As scarecrows are pretty expensive she wants to minimize the number of them. Can you count it for her?

Note: Even thought it might look like that from description, the formed "graph" doesn't have to be planar! Also multi-fields and self-field are not allowed.

Input

The first line contains an integer 1 ≤ T ≤ 100

Each of the next T test-cases begins with two integers 0 ≤ M ≤ 150, 1 ≤ N ≤ 150, the number of farmhouses and the number of fields.

Each of next M lines contains two numbers 0≤ Ai,Aj < N, the farmhouses, which are connected by a field.

Output

For each test-case output the minimal number of scarecrows Ada has to buy, to cover all fields.

Example Input

6
3 3
1 2
1 0
2 0
4 3
1 2
1 3
1 0
5 6
0 2
0 3
1 3
1 2
1 4
2 4
5 8
0 1
0 3
0 4
1 2
1 4
3 4
3 2
2 4
4 2
0 1
2 3
6 9
0 4
4 3
1 2
2 0
2 3
5 3
4 1
4 2
5 0

Example Output

2
1
3
3
2
3

Example Input 2

2
17 7
12 9
11 8
9 16
11 2
5 14
7 6
8 14
16 23
10 13
11 3
7 14
14 3
9 11
7 8
0 9
8 14
10 8
0 4
6 15
6 12
2 5
10 2
7 11
13 12
15 13
5 3
15 0
6 2
12 9
5 1
1 4

Example Output 2

4
9

hide comments
morass: 2019-05-10 11:19:56

@Witold Jarnicki: Repaired... thank you for pointing it out ^_^

Witold Jarnicki: 2019-05-06 16:40:09

It seems that there are test cases with M=0. The solution I submitted assumed that M>0 (indirectly by an assert) and it got rejected because of SIGABRT.

Min_25: 2017-06-16 13:15:45

@morass
Thank you for updating.

morass: 2017-06-16 12:28:28

@Min_25: Thank you very much! I updated the test-cases (hope I didn't replace any important one :/ ). Now it really TLE's (even though it is a dirty practice :D),

morass: 2017-06-16 11:47:17

@Min_25: Good day to you. Firstly sorry, but I'm affraid I didn't recognize the pattern of your inputs. So probably not included (I've tried to include some 3/4 regular graphs which shall be [imho] somehow around WC )

Can you please provide such pattern so I can reconsider the problem? Thank you! ^_^

Have nice day
~/Morass


Added by:Morass
Date:2017-06-16
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All