4 4 
1 2
2 3
3 4 
2 4

答案：
INF
20
18
20

#include <stdio.h>
#include <string.h>
#define MAX 150
#define INF 1000000000
struct Point{
	int x, y ;
}p[MAX*30] ;
int c[MAX][MAX];
int graph[MAX][MAX] , sum[MAX];
int dis[MAX] ;
bool visited[MAX] ;
int dijkstra(int n,int s)
{
	memset(visited,false,sizeof(visited)) ;
	for(int i = 1 ; i <= n ; ++i)
	{
		dis[i] = graph[s][i] ; 
	}
	dis[s] = 0 ;
	visited[s] = true ;
	int sumt = 0 ;
	for(int i = 1 ; i < n ; ++i)
	{
		int index = -1 , min = INF ;
		for(int j = 1 ; j <= n ; ++j)
		{
			if(!visited[j] && min>dis[j])
			{
				index = j ;
				min = dis[j] ;
			}
		}
		if(index == -1)
		{
			return INF ;
		}	
		sumt += min ;
		visited[index] = true ;
		for(int j = 1 ; j <= n ; ++j)
		{
			if(!visited[j] && dis[j]>dis[index]+graph[index][j])
			{
				dis[j] = dis[index] + graph[index][j] ;
			}
		}
	}
	return sumt ;
}

int main()
{
	int n , m ;
	while(~scanf("%d%d",&n,&m))
	{
		memset(c,0,sizeof(c)) ;
		for(int i = 0 ; i < MAX ; ++i)
		{
			for(int j = 0 ; j < MAX ; ++j)
			{
				graph[i][j] = INF ;
			}
		}
		for(int i = 0 ; i < m ; ++i)
		{
			int x , y ;
			scanf("%d%d",&x,&y) ; 
			p[i].x = x , p[i].y = y ;
			c[x][y]++ ,c[y][x]++ ;
			graph[x][y] = graph[y][x] = 1 ;
		}
		bool flag = true ;
		int ans = 0 ;
		for(int i = 1 ; i <= n ; ++i)
		{
			if(flag)
			{
				sum[i] = dijkstra(n,i) ;
				if(sum[i] == INF)
				{
					flag = false ;
				}
				ans += sum[i] ;
			}
			
		}
		for(int i = 0 ; i < m ; ++i)
		{
			if(!flag)
			{
				puts("INF") ;
			}
			else
			{
				if(c[p[i].x][p[i].y]>1)
				{
					printf("%d\n",ans) ;
				}
				else
				{
					graph[p[i].x][p[i].y] = graph[p[i].y][p[i].x] = INF ;
					int sumx = dijkstra(n,p[i].x) ;
					int sumy = dijkstra(n,p[i].y) ;
					if(sumx == INF || sumy == INF)
					{
						puts("INF") ;
					}
					else
					{
						printf("%d\n",ans+sumx+sumy-sum[p[i].x]-sum[p[i].y]) ;
					}
					graph[p[i].x][p[i].y] = graph[p[i].y][p[i].x] = 1 ;
				}
			}
		}
	}
	return 0 ;
}