Eva

Time Limit: 10 Sec  Memory Limit: 162 MB
Description

Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。

输入n<=100000 m<=500000及m条边

输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。

5 5
1 2
2 3
1 3
3 4
4 5

8
8
16
14
8

/**************************************************************

    Problem: 1123

    User: ictsing

    Language: C++

    Result: Accepted

    Time:936 ms

    Memory:27008 kb

****************************************************************/

 

//BZOJ1123 [POI2008]BLO

#include <iostream>

#include <cstdio>

using namespace std;

int ecnt=0;

const int mt = 500000+5 ;

int to[mt<<1],nxt[mt<<1],adj[mt],sz[mt];

long long ans[mt];

int dfn[mt],low[mt],_clock=0;

int n,m;

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

void adde(int u,int v)

{

    ecnt++,to[ecnt]=v,nxt[ecnt]=adj[u],adj[u]=ecnt;

}

void tarjan(int u)

{

    sz[u]=1;

    int t=0;

    dfn[u]=low[u]=++_clock;

    for(int i=adj[u];i;i=nxt[i])

    {

        int v=to[i];

        if(!dfn[v]) 

        {

            tarjan(v);

            sz[u]+=sz[v];

            low[u]=min(low[u],low[v]);

            if(dfn[u]<=low[v])

            {

                ans[u]+=1ll*t*sz[v];

                t+=sz[v];

            }

        }

        else low[u]=min(low[u],dfn[v]);

    }

    ans[u]+=1ll*t*(n-t-1);

}

int main()

{

    n=read(),m=read();

    for(int i=1;i<=m;i++)

    {

        int a=read(),b=read();

        adde(a,b),adde(b,a);

    }

    tarjan(1);

    for(int i=1;i<=n;i++)

        printf("%lld\n",(ans[i]+n-1)*2);

    return 0;

}