TOI12: weakpoint

#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9;
const int N = 5e5 + 10;
vector <int> g[N];
int n, p;

/// cycle
bool is_cycle[N];
int par[N], color[N];
bool Cycle(int u, int pre){
    if(color[u] == 2) return false;
    if(color[u] == 1){
        while(pre != u){
            is_cycle[pre] = true;
            pre = par[pre];
        }
        is_cycle[u] = true;
        return true;
    }
    color[u] = 1;
    par[u] = pre;
    for(auto v: g[u]){
        if(v == pre) continue;
        if(Cycle(v, u)) return true;
    }
    color[u] = 2;
    return false;
}

/// count node
int node[N];
int Count(int u, int pre){
    if(is_cycle[u]) return 0;
    if(node[u] != 0) return node[u];
    node[u] = 1;
    for(auto v: g[u]){
        if(pre != v)
            node[u] += Count(v, u);
    }
    return node[u];
}
void CountNode(){
    for(int u=1;u<=n;u++){
        if(is_cycle[u]){
            node[u] = 1;
            for(auto v: g[u])
                node[u] += Count(v, 0);
        }
    }
}

///
void Solve1(){
    int mx = -INF, ans_node = INF;
    for(int u=1;u<=n;u++){
        if(u == p) continue;
        if(node[u] > mx){
            mx = node[u];
            ans_node = u;
        }
        else if(node[u] == mx)
            ans_node = min(ans_node, u);
    }

    printf("%d\n%d", ans_node, mx - 1);
}

///
bool vs[N];
bool FindCycle(int st){
    queue <int> q;
    q.push(st);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        if(vs[u]) continue;
        vs[u] = true;
        if(is_cycle[u]) return true;
        for(auto v: g[u]) q.push(v);
    }
    return false;
}
void Solve2(){
    int mx = -INF, ans_node = INF;
    int sum = 0, cycle_node = -1;
    for(auto u: g[p]){
        if(cycle_node == -1 and FindCycle(u))
            cycle_node = u;
        else{
            sum += node[u];
            if(node[u] > mx){
                mx = node[u];
                ans_node = u;
            }
            else if(mx == node[u])
                ans_node = min(ans_node, u);
        }
    }

    int count_cycle_node = n - sum - 1;
    if(count_cycle_node > mx){
        mx = count_cycle_node;
        ans_node = cycle_node;
    }
    else if(count_cycle_node == mx)
        ans_node = min(ans_node, cycle_node);

    printf("%d\n%d", ans_node, mx - 1);
}

int main(){

    scanf("%d%d", &n, &p);

    for(int i=1;i<=n;i++){
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    Cycle(1, 0);

    CountNode();

    if(is_cycle[p]) Solve1();
    else Solve2();

    return 0;
}

/**

15 12
1 2
2 3
2 4
4 15
15 6
4 5
5 7
6 7
8 5
5 9
7 10
7 11
6 12
12 13
12 14

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

**/