#include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define Maxn 10010

 int n,m;

 int first[Maxn],low[Maxn],dfn[Maxn],fa[Maxn],son[Maxn];

 int cut[Maxn];

 int cnt;

 struct node

 {

     int x,y,next;

 };

 node t[Maxn*],ans[Maxn];

 int len;

 int mymin(int x,int y) {return x<y?x:y;}

 void ins(int x,int y)

 {

     t[++len].x=x;t[len].y=y;

     t[len].next=first[x];first[x]=len;

 }

 bool cmp(node x,node y) {return (x.x==y.x)?(x.y<y.y):(x.x>y.x);}

 void ffind(int x,int f)

 {

     dfn[x]=low[x]=++cnt;

     fa[x]=f;

     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)

     {

         int y=t[i].y;

         if(dfn[y]==)

         {

             ffind(y,x);

             son[x]++;

             low[x]=mymin(low[x],low[y]);

             if(low[y]>=dfn[x]) cut[x]++;

         }

         else low[x]=mymin(low[x],dfn[y]);

     }

 }

 int main()

 {

     while()

     {

         scanf("%d%d",&n,&m);

         if(n==&&m==) break;

         len=;cnt=;

         memset(first,,sizeof(first));

         while()

         {

             int a,b;

             scanf("%d%d",&a,&b);

             if(a==-&&b==-) break;

             a++;b++;

             ins(a,b);ins(b,a);

         }

         memset(dfn,,sizeof(dfn));

         memset(cut,,sizeof(cut));

         memset(son,,sizeof(son));

         ffind(,);ans[].y=;

         if(son[]>) ans[].x=son[];

         else ans[].x=;

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

         {

             ans[i].y=i-;

             ans[i].x=cut[i]+;

         }

         sort(ans+,ans++n,cmp);

         for(int i=;i<=m;i++) printf("%d %d\n",ans[i].y,ans[i].x);

         printf("\n");

     }

     return ;

 }