TUMSO16: Fast Aid

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 5;

vector<int> adj[N];
int disc[N], low[N], dp[N], mx, ansU, ansV;
bool visited[N];

int discCnt = 0;
void DFS(int u, int p){
    disc[u] = ++discCnt;
    low[u] = disc[u];
    visited[u] = true;
    int cnt = 1;
    for(int v : adj[u]){
        if(v == p){
            continue;
        }
        if(visited[v]){
            low[u] = min(low[u], disc[v]);
        } else {
            DFS(v, u);
            low[u] = min(low[u], low[v]);
            cnt += dp[v];
            if(low[v] > disc[u]){
                if(dp[v] > mx){
                    mx = dp[v];
                    ansU = u;
                    ansV = v;
                } else if(dp[v] == mx){
                    if(u + v < ansU + ansV){
                        ansU = u;
                        ansV = v;
                    } else if(u + v == ansU + ansV){
                        if(min(u, v) < min(ansU, ansV)){
                            ansU = u;
                            ansV = v;
                        }
                    }
                }
            }
        }
    }
    dp[u] = cnt;
}

int main(){

    int nVertex, nEdge;
    scanf("%d%d", &nVertex, &nEdge);
    for(int i = 1; i <= nEdge; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    DFS(1, 0);
    if(mx == 0){
        cout << "OK!";
    } else {
        cout << min(ansU, ansV) << ' ' << max(ansU, ansV);
    }

    return 0;
}