OBI Ciclovias https://olimpiada.ic.unicamp.br/pratique/pu/2016/f2/ciclovias/

a.cpp

#include <bits/stdc++.h>
#define ii pair<int,int>
using namespace std;

const int N = 1e5+20;
int n,m;
vector<int> adj[N];
ii dist[N];

int i;

ii get_val(int x, int last) {
    ii ans={1,-1};

    for(auto y : adj[x]) {
        if(y > last) {
            
            int v;
            if(y > i && dist[y].second > x) {
                v = dist[y].first;
            } else {
                ii p = get_val(y,x);
                v = p.first;
            }

            if(1+v > ans.first) {
                ans = {1+v,y};
            }
        }
    }

    return ans;
}

int main() {

    cin>>n>>m;

    for(int i=0;i<m;i++) {
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for(i=n;i>0;i--) {
        dist[i] = get_val(i,-1);
    }

    for(int i=1;i<=n;i++) {
        printf("%d%c",dist[i].first,i==n?'\n':' ');
    }


    return 0;
}