1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map>10 using namespace std;11 12 const int maxn=1e4+5;13 14 struct node15 {16     int id;17     int ge;18 }d[maxn];19 20 int n,m;21 int pre[maxn],cut[maxn],low[maxn];22 int degree[maxn];23 int dfs_block;24 vector<int> G[maxn];25 26 int dfs(int u,int fa)27 {28     int lowu=pre[u]=++dfs_block;29     int child=0;30     for(int i=0;i<G[u].size();i++)31     {32         int v=G[u][i];33         if(!pre[v])34         {35             child++;36             int lowv=dfs(v,u);37             lowu=min(lowu,lowv);38             if(lowv>=pre[u])39             {40                 cut[u]++;41             }42         }43         else if(pre[v]<pre[u] && v!=fa)44             lowu=min(lowu,pre[v]);45     }46     if(fa < 0 && child==1)  cut[u]=1;47     low[u]=lowu;48     return lowu;49 }50 51 bool cmp(node a,node b)52 {53     return a.ge>b.ge||(a.ge==b.ge&&a.id<b.id);54 }55 56 int main()57 {58     //freopen("D:\\input.txt","r",stdin);59     while(~scanf("%d%d",&n,&m)&& n && m)60     {61         for(int i=0;i<n;i++)  {G[i].clear();cut[i]=1;}62         int u,v;63         while(true)64         {65             scanf("%d%d",&u,&v);66             if(u==-1 && v==-1) break;67             G[u].push_back(v);68             G[v].push_back(u);69         }70         memset(pre,0,sizeof(pre));71         memset(low,0,sizeof(low));72         dfs(0,-1);73         for(int i=0;i<n;i++)74         {75             d[i].id=i;76             d[i].ge=cut[i];77         }78         sort(d,d+n,cmp);79         for(int i=0;i<m;i++)80             printf("%d %d\n",d[i].id,d[i].ge);81         printf("\n");82     }83     return 0;84 }