TOI12: weakpoint (Tarjan)

#include <bits/stdc++.h>

using namespace std;
const int N = 5e5 + 10;
vector <int> g[N];
int ans_max = 0, ans_node = N;
int disc[N], low[N];
bool vs[N];

int dis_cnt = 0;
int tarjan(int u, int pre){

    dis_cnt ++;
    disc[u] = low[u] = dis_cnt;
    vs[u] = true;
    int node_cnt = 1;
    bool is_art = false;
    int art_cnt = 0;

    for(auto v: g[u]){
        if(pre == v) continue;
        if(!vs[v]){
            int node_v_cnt = tarjan(v, u);
            node_cnt += node_v_cnt;
            low[u] = min(low[u], low[v]);
            if(pre != 0 and low[v] >= disc[u]){
                is_art = true;
                art_cnt += node_v_cnt;
            }
        }
        else{
            low[u] = min(low[u], disc[v]);
        }
    }

    if(is_art){
        if(art_cnt > ans_max){
            ans_max = art_cnt;
            ans_node = u;
        }
        else if(art_cnt == ans_max)
            ans_node = min(ans_node, u);
    }

    return node_cnt;
}

int main(){

    int n, m;
    scanf("%d%d", &n, &m);

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

    tarjan(m, 0);

    if(ans_max == 0) printf("%d\n0", m == 1 ? 2: 1);
    else printf("%d\n%d", ans_node, ans_max);

    return 0;
}