#include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<stack>

 using namespace std;

 const int MAXN= ;

 struct Edge{

     int u,v;

     Edge(){}

     Edge(int _u,int _v):u(_u),v(_v){}

 };

 struct Cut{

     int c,w;

 }cut[MAXN];

 int iscut[MAXN],pre[MAXN],low[MAXN],dfs_clock,bcc_cnt,bccno[MAXN];

 int son;

 vector<int >G[MAXN],bcc[MAXN];

 stack<Edge>stk;

 void dfs(int u,int fa)

 {

     pre[u]=low[u]=dfs_clock++;

     son=;

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

     {

         int v=G[u][i];

         Edge e=Edge(u,v);

         if(!pre[v]){

             stk.push(e);

             son++;

             dfs(v,u);

             low[u]=min(low[u],low[v]);

             if(low[v]>=pre[u]){

                 iscut[u]=;

                 bcc_cnt++;

                 bcc[bcc_cnt].clear();

                 while()

                 {

                     Edge x=stk.top();

                     stk.pop();

                     if(bccno[x.u]!=bcc_cnt){

                         bcc[bcc_cnt].push_back(x.u);

                         bccno[x.u]=bcc_cnt;

                     }

                     if(bccno[x.v]!=bcc_cnt){

                         bcc[bcc_cnt].push_back(x.v);

                         bccno[x.v]=bcc_cnt;

                     }

                     if(x.u==u&&x.v==v)

                         break;

                 }

             }

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

             stk.push(e);

             low[u]=min(low[u],pre[v]);

         }

     }

     if(fa==-&&son==)

         iscut[u]=;

 }

 void find_bcc(int n)

 {

     bcc_cnt=dfs_clock=;

     memset(pre,,sizeof(pre));

     memset(bccno,,sizeof(bccno));

     memset(iscut,,sizeof(iscut));

     memset(cut,,sizeof(cut));

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

         if(!pre[i])

             dfs(i,-);

 }

 int cmp(Cut a,Cut b)

 {

     if(a.w==b.w)

         return a.c<b.c;

     return a.w>b.w;

 }

 int main()

 {

     int n,m,x,y;

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

     {

         if(!n&&!m)

             return ;

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

             G[i].clear();

         while()

         {

             scanf("%d%d",&x,&y);

             if(x==-&&y==-)

                 break;

             G[x].push_back(y);

             G[y].push_back(x);

         }

         find_bcc(n);

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

         {

             for(int j=;j<bcc[i].size();j++)

             {

                 cut[bcc[i][j]].c=bcc[i][j];

                 cut[bcc[i][j]].w++;

             }

         }

         sort(cut,cut+n,cmp);

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

             printf("%d %d\n",cut[i].c,cut[i].w);

         puts("");

     }

     return ;

 }