TUMSO-16: Fast Aid

#include <bits/stdc++.h>

using namespace std;
const int N = 1e4 + 10;
const int K = 1e4 + 10;
const int INF = 1e9;
vector <int> g[N];
int disc[N], low[N];
bool vs[N];
int mx = -INF, ans_u, ans_v;

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

    vs[u] = true;
    dis_cnt ++;
    disc[u] = low[u] = dis_cnt;

    int node_cnt = 1;
    for(auto v: g[u]){
        if(v == pre) continue;
        if(!vs[v]){
            int node_v_cnt = tarjan(v, u);
            node_cnt += node_v_cnt;
            low[u] = min(low[u], low[v]);
            if(low[v] > disc[u]){
                int cur_u = u, cur_v = v;
                if(cur_u > cur_v) swap(cur_u, cur_v);
                if(node_v_cnt > mx){
                    mx = node_v_cnt;
                    ans_u = cur_u;
                    ans_v = cur_v;
                }
                else if(node_v_cnt == mx){
                    if(cur_u + cur_v < ans_u + ans_v){
                        ans_u = cur_u;
                        ans_v = cur_v;
                    }
                    else if(cur_u + cur_v == ans_u + ans_v and cur_u < ans_u){
                        ans_u = cur_u;
                        ans_v = cur_v;
                    }
                }
            }
        }
        else{
            low[u] = min(low[u], disc[v]);
        }
    }

    return node_cnt;
}

int main(){

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

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

    tarjan(1, 0);

    if(mx == -INF)
        printf("OK!");
    else
        printf("%d %d", ans_u, ans_v);

    return 0;
}