Submission #371288

---

Source Code Expand

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define reps(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reps(i,0,n)

using namespace std;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;

vvi G;
vector<int> color;

bool func(int v, int par, int c)
{
    color[v] = c;

    for(int u : G[v]){
        if(u==par) continue;
        if(color[u] == -1){
            if(!func(u, v, !c)) return false;
        }
        else{
            if(color[u] == c) return false;
        }
    }

    return true;
}

signed main()
{
    int n;
    cin >> n;
    G.resize(n);
    color.assign(n, -1);

    rep(i, n){
        int a, b;
        cin >> a >> b;
        --a; --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    cout << "1 " << (func(0, -1, 0) ? n : n-1) << endl;
}

Submission Info

Judge Result