CUBE-190: Supernova

#include <bits/stdc++.h>;

using namespace std;
using pi = pair <int, int>;
using lli = long long;
int n, m;
vector <pi> g[100010];
pi path[100010];
int color[100010], parent[100010];
bool Cycle[100010];
bool cycle;

void CYCLE(int u, int pre){
    if(color[u] == 2) return;
    if(color[u] == 1){
        cycle = true;
        int cur = pre;
        Cycle[u] = true;
        while(cur != u){
            Cycle[cur] = true;
            cur = parent[cur];
        }
        return ;
    }
    parent[u] = pre;
    color[u] = 1;
    for(auto v: g[u]){
        if(v.first != pre) {
            CYCLE(v.first, u);
        }
    }
    color[u] = 2;
}

int node[100010];
lli ans[100010];

int NODE(int u, int pre, int i){
    if(Cycle[u] and i != 0) return 0;
    node[u] = 1;
    for(auto v: g[u]){
        if(v.first != pre) node[u] += NODE(v.first, u, v.second);
    }
    ans[i] = (lli) (n - node[u]) * node[u];
    return node[u];
}

int main(){

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

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

    for(int i=1;i<=n;i++){
        CYCLE(i, 0);
        if(cycle) break;
    }


    for(int i=1;i<=n;i++){
        if(Cycle[i]) NODE(i, 0, 0);
    }

    for(int i=1;i<=n;i++){
        if(Cycle[path[i].first] and Cycle[path[i].second]) printf("0");
        else printf("%lld", ans[i]);
        printf(" ");
    }

    return 0;
}
/*
6 6
1 2
2 3
2 4
3 4
4 5
5 6

11 11
1 2
1 3
1 5
3 4
4 5
3 6
6 10
3 7
7 9
7 8
7 11

10 10
4 3
8 1
6 8
8 5
7 9
5 3
4 9
2 5
2 10
3 10

21 9 9 21 9 0 16 0 0 0

*/