#include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 using namespace std;

 const int maxn=1e4+;

 struct node

 {

     int id;

     int ge;

 }d[maxn];

 int n,m;

 int pre[maxn],cut[maxn],low[maxn];

 int degree[maxn];

 int dfs_block;

 vector<int> G[maxn];

 int dfs(int u,int fa)

 {

     int lowu=pre[u]=++dfs_block;

     int child=;

     for(int i=;i<G[u].size();i++)

     {

         int v=G[u][i];

         if(!pre[v])

         {

             child++;

             int lowv=dfs(v,u);

             lowu=min(lowu,lowv);

             if(lowv>=pre[u])

             {

                 cut[u]++;

             }

         }

         else if(pre[v]<pre[u] && v!=fa)

             lowu=min(lowu,pre[v]);

     }

     if(fa <  && child==)  cut[u]=;

     low[u]=lowu;

     return lowu;

 }

 bool cmp(node a,node b)

 {

     return a.ge>b.ge||(a.ge==b.ge&&a.id<b.id);

 }

 int main()

 {

     //freopen("D:\\input.txt","r",stdin);

     while(~scanf("%d%d",&n,&m)&& n && m)

     {

         for(int i=;i<n;i++)  {G[i].clear();cut[i]=;}

         int u,v;

         while(true)

         {

             scanf("%d%d",&u,&v);

             if(u==- && v==-) break;

             G[u].push_back(v);

             G[v].push_back(u);

         }

         memset(pre,,sizeof(pre));

         memset(low,,sizeof(low));

         dfs(,-);

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

         {

             d[i].id=i;

             d[i].ge=cut[i];

         }

         sort(d,d+n,cmp);

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

             printf("%d %d\n",d[i].id,d[i].ge);

         printf("\n");

     }

     return ;

 }