ADACROW - Ada and Scarecrow

no tags 

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 disasterous, 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 1 ≤ N, M ≤ 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
[Rampage] Blue.Mary: 2017-06-20 05:56:18

[Deleted After AC.]

Last edit: 2017-06-20 09:04:03
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),

Min_25: 2017-06-16 12:05:31

@morass:
[removed]

Last edit: 2017-06-20 19:28:04
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

Min_25: 2017-06-16 11:03:54

[Edit]
removed.

Last edit: 2017-06-16 14:14:24
[Rampage] Blue.Mary: 2017-06-16 04:51:16

[Deleted After AC.]

Last edit: 2017-06-20 09:04:18

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