CUBE-190: Supernova

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll n,m;
const ll N = 100005;
vector<ll> G[N];
ll color[N];
ll par[N],mark[N],dp[N];
pair<ll,ll> edge[N];
ll nt = 0;

long long dfs(ll p , ll u){
    if(dp[u])
        return dp[u];
    long long ans = 1;
    for(auto c : G[u]){
        if(c != p and !mark[c])
            ans += dfs(u,c);
    }
    dp[u] = ans;
    return ans;
}

void cycle(ll p , ll u){
    if(color[u] == 2)
        return ;
    if(color[u] == 1){
        ll cur = p;
        mark[cur] = 1;
        while(cur != u){
            cur = par[cur];
            mark[cur] = 1;
            nt++;
        }
        return;
    }
    par[u] = p;
    color[u] = 1;
    for(auto v : G[u]){
        if(v == par[u])
            continue;
        cycle(u,v);
    }
    color[u] = 2;
}

int main(){
    scanf("%lld%lld",&n,&m);
    for(ll i = 1 ; i <= n ; ++i){
        ll u,v;
        scanf("%lld%lld",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
        edge[i] = {u,v};
    }
    cycle(0,1);
    for(long long i = 1 ; i <= n ; ++i){
        if(mark[i])
            dfs(0,i);
    }
    for(ll i = 1 ; i <= m ; ++i){
        ll u = edge[i].first;
        ll v = edge[i].second;
        if(mark[u] and mark[v])
            printf("0 ");
        else{
            long long cnt = min(dp[v],dp[u]);
            printf("%lld ",cnt * (n-cnt));
        }
    }
}