SuperNova

#include<stdio.h>
#include<vector>
using namespace std;
int n,m;
typedef long long int ll;
int const N = 100010;
vector<int> adj[N];

int color[N];

int deg[N];
bool cycle[N];
bool nearstart[N];

int dfscycle(int u,int prev){
    if(color[u] != 0){
    //  printf("found %d\n",u);
        return u;
    }
    color[u] = prev;
    int ans = -1;
    for(int i = 0 ; i < adj[u].size() ; i ++){
        int v = adj[u][i];
        if(v != prev){
            int val = dfscycle(v,u);
            if(val != -1)ans = val;
        }
    }
    return ans;
}

ll val[N];
int visited[N];
ll dfs(int u){
//  if(cycle[u])return 0;
//  if(visited[u])return 0;

    visited[u] = true;
//  printf("Test count subtree : %d -> ",u);
    for(int i = 0 ; i < adj[u].size() ; i ++){
        int v = adj[u][i];
        if(!cycle[v] && !visited[v]){
//          printf("%d ",v);
            val[u] += dfs(v);
        }
    }
//  printf("\n");
    return val[u] = val[u] + 1;
}

int main()
{
    scanf("%d %d",&n,&m);
    pair<int,int> edge[m+1];
    int startdfs = -1;
    for(int i = 0 ; i < m ; i ++){
        int u,v;
        scanf("%d %d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
        edge[i] = {u,v};
        deg[u]++;
        deg[v]++;
    }

    for(int i = 1 ; i <= n ; i ++){
        if(deg[i] == 1){
            startdfs = i;
        }
    }
    if(startdfs == -1){ //no leaf
        for(int i = 0 ; i < m ; i++)printf("0 ");
        return 0;
    }
//  printf("Test start dfs %d\n",startdfs);
    int start = dfscycle(startdfs,-1);
    //start = dfscycle(start,-1);
/*  printf("Test start %d\nParent : ",start);
    for(int i = 1 ; i <= n ; i ++){
        printf("%d ",color[i]);
    }printf("\n");
*///    printf("Test nearstart : ");
    for(int i = 0 ; i < adj[start].size() ; i ++){
        int ne = adj[start][i];
        nearstart[ne] = true;
    //  printf("%d ",ne);
    }//printf("\n");
//  printf("Start cycle : %d\n",start);
    cycle[start] = true;
    int si = color[start];
//  printf("Test si %d\n",si);
    int cnt = 0;
    while(cnt != 2){
        if(nearstart[si])cnt++;
    //  if(cnt == 2)break;
    //  printf("Into  cycle : %d\n",si);
        if(si == -1)break;
        cycle[si] = true;
        si = color[si];
    }
    //printf("Test ");
//  printf("Cycle : ");

    for(int i = 1 ; i <= n ; i ++){
        if(!cycle[i])continue;
    //  if(cycle[i])printf("%d ",i);
        dfs(i);
        val[i] = 1e18;
    }
/*  for(int i = 1 ; i <= n ; i ++){
        printf("%lld ",val[i]);
    }printf("\n");*/
    for(int i = 0 ; i < m ; i ++){
        ll x = min(val[edge[i].first],val[edge[i].second]);
        if(x == 1e18){
            printf("0");
        }else{
            printf("%lld",(n-x)*x);
        }
        printf(" ");
    }
    //while(!cycle[si])
    return 0;
}
/*
6 6
1 2
1 3
1 4
2 3
2 5
3 6

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

2 2
1 2
2 1

3 3
1 2
2 3
3 1
*/