#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#define MAX 10003
using namespace std;

vector<int>G[MAX];
int low[MAX],d[MAX],visited[MAX],cutpoint[MAX],dtime;
pair<int,int>result[MAX];

bool compare(pair<int,int>a,pair<int,int>b)
{
    if(a.second==b.second)
    return a.first<b.first;
    return a.second>b.second;
}
void DFS(int u,int parent =-1)
{
    int i,v,child=0;
    bool art=false;
    low[u]=d[u]=visited[u]=++dtime;
    for(i=0;i<G[u].size();++i)
    {
        v=G[u][i];
        if(v==parent)
        continue;
        if(visited[v])
        low[u]=min(low[u],d[v]);
        else
        {
            DFS(v,u);
            ++child;
            low[u]=min(low[u],low[v]);
            if(low[v]>=d[u])
                art=true;
        }
    }
    if(art&&parent>-1)
    cutpoint[u]=child+1;
    else
    cutpoint[u]=1;
    if(parent==-1&&child>1)
    cutpoint[u]=child;
}

int main()
{
    int n,m,i,a,b;
    while(cin>>n>>m,n)
    {
        memset(low,0,sizeof(low));
        memset(d,0,sizeof(d));
        memset(visited,0,sizeof(visited));
        memset(cutpoint,0,sizeof(cutpoint));
        for(i=0;i<=n;++i)
        G[i].clear();
        while(cin>>a>>b,a!=-1)
        {
            G[a].push_back(b);
            G[b].push_back(a);
        }
        dtime=0;
        DFS(0);
        for(i=0;i<n;++i)
        {
            result[i].first=i;
            result[i].second=cutpoint[i];
        }
        sort(result,result+n,compare);
        for(i=0;i<m;++i)
        cout<<result[i].first<<" "<<result[i].second<<endl;
        cout<<endl;
    }
    return 0;
}