UVa 11080 - Place the Guards Solution

#include <vector>
#include <iostream>
using namespace std;
int n,e,ans,comp;
vector<vector<int> > rel;
vector<int> vis;
int dfs(int i,int col){
    if(vis[i]==(1-col))
        return 0;
    if(vis[i]==col)
        return 1;
    vis[i]=col;
    comp++;
    if(col)
        ans++;
    int flag=1;
    for(int j=0;j<rel[i].size();j++){
        flag&=dfs(rel[i][j],1-col);
    }
    return flag;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>e;
        vis.assign(n,-1),rel.assign(n,vector<int>());
        for(int i=0;i<e;i++){
            int x,y;
            cin>>x>>y;
            rel[x].push_back(y);
            rel[y].push_back(x);
        }
        int flag=0,fans=0;
        for(int i=0;i<n;i++){
            if(vis[i]==-1){
                comp=0,ans=0;
                if(!dfs(i,0)){
                    flag=1;
                    break;
                }
                if(comp==1)
                    fans+=1;
                else{
                    fans+=((ans>comp/2)?(comp-ans):ans);
                }
            }
        }
        if(flag)
            cout<<-1<<endl;
        else cout<<fans<<endl;
    }
}