Submission #371310

---

Source Code Expand

import java.util.ArrayList;
import java.util.Scanner;

class C {
    public static void main(String... args) {
        final Scanner sc = new Scanner(System.in);
        final int n = sc.nextInt();
        final V[] vs = new V[n];
        for (int i = 0; i < n; i++)
            vs[i] = new V();
        for (int i = 0; i < n; i++) {
            final int a = sc.nextInt() - 1;
            final int b = sc.nextInt() - 1;
            vs[a].add(vs[b]);
            vs[b].add(vs[a]);
        }

        for (final V v : vs) {
            final int loop = dfs(v, 0);
            if (loop > 0) {
                final int min = loop == n ? 2 : 1;
                final int MAX = loop % 2 == 0 ? n : n - 1;
                System.out.printf("%d %d\n", min, MAX);
                return;
            }
        }
        throw null;
    }

    static class V extends ArrayList<V> {
        int depth = -1;
    }

    static int dfs(final V v, final int depth) {
        if (v.depth >= 0)
            return depth - v.depth > 2 ? depth - v.depth : 0;
        else {
            v.depth = depth;
            for (final V next : v) {
                final int res = dfs(next, depth + 1);
                if (res > 0)
                    return res;
            }
            return 0;
        }
    }
}
public class Main {
    public static void main(String...args) {
        C.main();
    }
}

Submission Info

Judge Result