Submission #371510

---

Source Code Expand

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

vector<int> g[128000];
int d[128000];

void dfs(int v, int c) {
  if (d[v] >= 0) return;
  d[v] = c;
  for (int i : g[v]) dfs(i, c+1);
}

int main() {
  int n;
  cin >> n;
  REP(i,n) {
    int a, b;
    cin >> a >> b; --a; --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  bool flag1 = false;
  REP(i,n) {
    if (g[i].size() == 1) flag1 = true;
  }
  if (flag1) cout << 1 << " ";
  else cout << 2 << " ";
  memset(d, -1, sizeof(d));
  dfs(0, 0);
  bool flag2 = false;
  REP(i,n) {
    for (int j : g[i]) {
      if ((d[i] + d[j]) % 2 == 0) flag2 = true;
    }
  }
  if (flag2) cout << n-1 << endl;
  else cout << n << endl;
  return 0;
}

Submission Info

Judge Result