Problem

In the country of Ajabdesh there are some streets and junctions. Each street connects 2 junctions. The king of Ajabdesh wants to place some guards in some junctions so that all the junctions and streets can be guarded by them. A guard in a junction can guard all the junctions and streets adjacent to it. But the guards themselves are not gentle. If a street is guarded by multiple guards then they start fighting. So the king does not want the scenario where a street may be guarded by two guards. Given the information about the streets and junctions of Ajabdesh, help the king to find the minimum number of guards needed to guard all the junctions and streets of his country.

Input

The first line of the input contains a single integer T (T < 80) indicating the number of test cases. Each test case begins with 2 integers v (1 ≤ v ≤ 200) and e (0 ≤ e ≤ 10000.). v is the number of junctions and e is the number of streets. Each of the next e line contains 2 integer f and t denoting that there is a street between f and t. All the junctions are numbered from 0 to v − 1.

Output

For each test case output in a single line an integer m denoting the minimum number of guards needed to guard all the junctions and streets. Set the value of m as ‘-1’ if it is impossible to place the guards without fighting.

Sample Input

2
4 2
0 1
2 3
5 5
0 1
1 2
2 3
0 4
3 4

Sample Output

2
-1

문제 풀이

최소 가드수 구하는 문제이다.
연결된 간선 중 하나에 가드를 설치해야되는데,
최소 가드수를 구해야되기 때문에, 양쪽중 하나를 잘 선택해야 된다.

이분 그래프 검사를 이용하는 데 추가적인 조건 하나를 추가해서 풀었다.

답안 코드

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAX_V   200

int v, e;

vector<int> adj[MAX_V];
int color[MAX_V];
int q[MAX_V], wq, rq;

int main(){
    int T;
    scanf("%d\n", &T);
    while(T--){
        scanf("%d %d\n", &v, &e);
        int a,b;
        for(int i = 0; i < e; ++i){
            scanf("%d %d\n", &a, &b);
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        
        int min_guard = 0;
        memset(color,-1,sizeof(color));
        wq = rq = 0;
        for(int i = 0; i < v && min_guard != -1; ++i){
            if(color[i] != -1)  continue;
            
            int v_count = 1;
            int guard = 1;
            color[i] = 1;
            q[wq++] = i;
            while(wq > rq){
                int u = q[rq++];
                
                for(int j = 0; j < adj[u].size(); ++j){
                    int k = adj[u][j];
                    if(color[k] == -1){
                        q[wq++] = k;
                        color[k] = 1 - color[u];
                        if(color[k] == 1)
                            guard++;
                        v_count++;
                    }
                    else if(color[k] == color[u]){
                        min_guard = -1;
                        rq = wq;
                        break;
                    }
                }
            }
            
            if(min_guard != -1){
                min_guard += (guard == v_count) ? guard : min(guard, v_count-guard);
            }
        }
        
        printf("ans (%d)\n", min_guard);
        
        for(int i = 0; i < v; ++i)
            adj[i].clear();
    }
    return 0;
}