Travel

/*
由于每条边的长度都是1，可以用bfs来找出单源最短路最后在把所有的单源最短路加起来。优化，去掉边时先判断这条边
是否是某一点最短路中必须要用到的边，若果是，看看这条边有没有重边，如果也没有重边就只能把那一个点的最短路
重新求一次。
*/
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
int n,m,mp[102][102],use[102][102][102],vis[102],dis[102],sum[102];//mp[i][j]记录i到j路径条数，use[x][i][j]
//记录x的单源最短路中需不需要用到i和j,sum[i]记录i的单源最短路长度。
int a[3003],b[3003];
vector<int>v[102];
void init()
{
    memset(mp,0,sizeof(mp));
    memset(sum,0,sizeof(sum));
    memset(use,0,sizeof(use));
    for(int i=1;i<=100;i++){
        v[i].clear();
    }
}
int bfs(int x,int f)
{
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    queue<int>q;
    q.push(x);
    vis[x]=1;
    while(!q.empty()){
        int y=q.front();
        q.pop();
        for(int i=0;i<v[y].size();i++){
            int z=v[y][i];
            if(vis[z]) continue;
            if(mp[y][z]<=0) continue;//y到z之间是否联通
            dis[z]=dis[y]+1;
            vis[z]=1;
            q.push(z);
            if(!f){           //第一次算最短路时标记x的单源最短路要用到y,z。
                use[x][y][z]=1;
                use[x][z][y]=1;
            }
        }
    }
    int s=0;        //求总的最短路
    for(int i=1;i<=n;i++){
        if(i==x) continue;
        if(dis[i]==0){
            return -1;
        }
        s+=dis[i];
    }
    return s;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
        init();
        for(int i=0;i<m;i++){
            scanf("%d%d",&a[i],&b[i]);
            mp[a[i]][b[i]]++;
            mp[b[i]][a[i]]++;
            v[a[i]].push_back(b[i]);
            v[b[i]].push_back(a[i]);
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            sum[i]=bfs(i,0);
            if(sum[i]==-1){
                ans=-1;
                break;
            }
            ans+=sum[i];
        }
        for(int i=0;i<m;i++){
            if(ans==-1){       //如果数据本身就不能全部连通
                printf("INF\n");
                continue;
            }
            mp[a[i]][b[i]]--;    //去掉边ab
            mp[b[i]][a[i]]--;  
            if(mp[a[i]][b[i]]>0){  //存在重边，还可以连通
                printf("%d\n",ans);
            }
            else{
                int anss=ans;
                for(int j=1;j<=n;j++){
                    if(use[j][a[i]][b[i]]==0)  //用不到就不用重新计算了
                        continue;
                    int tem=bfs(j,1);
                    if(tem==-1){   //不能连通了
                        anss=-1;
                        break;
                    }
                    anss-=sum[j];
                    anss+=tem;
                }
                if(anss==-1) printf("INF\n");  
                else printf("%d\n",anss);
            }
            mp[a[i]][b[i]]++;
            mp[b[i]][a[i]]++;
        }
    }
    return 0;
}