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
|
|
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 )
|
Added by: | Morass |
Date: | 2017-06-16 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |