1 /*
 2 Author:    Leo.W
 3 Descriptipn:    給定幾個(gè)頂點(diǎn)以及已知某幾個(gè)頂點(diǎn)存在通路，求最少還需幾條路即可完成連通圖
 4 How to Do:    由最后一組測(cè)試數(shù)據(jù)易知999 0，且結(jié)合最小生成樹的知識(shí)可得，連通分量數(shù)減一即得解
 5   */
 6 #include <iostream>
 7 #include <stdio.h>
 8 #include <string.h>
 9 using namespace std;
10 #define MAXSIZE 1000
11 int path[MAXSIZE][MAXSIZE];
12 bool appear[MAXSIZE];
13 bool chose[MAXSIZE];
14 int m,n,lt;//圖中連線后的連通分量數(shù)
15 
16 void bfs(int num){
17     chose[num]=true;
18     int i;
19     for(i=1;i<=m;i++)
20         if(i!=num&&path[num][i]==0&&!chose[i]){//點(diǎn)i與點(diǎn)num有連線，并且點(diǎn)i還未被選入集合
21             lt--;    bfs(i);
22         }
23 }
24 int main(){
25     //freopen("in.txt","r",stdin);
26     while(scanf("%d",&m),m){//城鎮(zhèn)數(shù)
27         scanf("%d",&n);//已有的公路條數(shù)
28         lt=m;
29         memset(appear,false,MAXSIZE);
30         memset(chose,false,MAXSIZE);
31         int i,j;
32         for(i=1;i<=m;i++){
33             for(j=1;j<=m;j++)
34                 path[i][j]=MAXSIZE;
35         }
36         for(i=0;i<n;i++){
37             int begin,end;
38             scanf("%d%d",&begin,&end);
39             appear[begin]=appear[end]=true;//表示已經(jīng)連上線的點(diǎn),即已經(jīng)出現(xiàn)
40             path[begin][end]=path[end][begin]=0;
41         }
42         for(i=1;i<=m;i++)
43             if(appear[i]&&!chose[i]){
44                 bfs(i);
45             }
46         printf("%d\n",lt-1);
47     }
48     return 0; 
49 }