#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;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8YWxnb3JpdGhtPgojaW5jbHVkZTxjc3RyaW5nPgojZGVmaW5lIE1BWCAxMDAwMwp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdmVjdG9yPGludD5HW01BWF07CmludCBsb3dbTUFYXSxkW01BWF0sdmlzaXRlZFtNQVhdLGN1dHBvaW50W01BWF0sZHRpbWU7CnBhaXI8aW50LGludD5yZXN1bHRbTUFYXTsKCmJvb2wgY29tcGFyZShwYWlyPGludCxpbnQ+YSxwYWlyPGludCxpbnQ+YikKewogICAgaWYoYS5zZWNvbmQ9PWIuc2Vjb25kKQogICAgcmV0dXJuIGEuZmlyc3Q8Yi5maXJzdDsKICAgIHJldHVybiBhLnNlY29uZD5iLnNlY29uZDsKfQp2b2lkIERGUyhpbnQgdSxpbnQgcGFyZW50ID0tMSkKewogICAgaW50IGksdixjaGlsZD0wOwogICAgYm9vbCBhcnQ9ZmFsc2U7CiAgICBsb3dbdV09ZFt1XT12aXNpdGVkW3VdPSsrZHRpbWU7CiAgICBmb3IoaT0wO2k8R1t1XS5zaXplKCk7KytpKQogICAgewogICAgICAgIHY9R1t1XVtpXTsKICAgICAgICBpZih2PT1wYXJlbnQpCiAgICAgICAgY29udGludWU7CiAgICAgICAgaWYodmlzaXRlZFt2XSkKICAgICAgICBsb3dbdV09bWluKGxvd1t1XSxkW3ZdKTsKICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBERlModix1KTsKICAgICAgICAgICAgKytjaGlsZDsKICAgICAgICAgICAgbG93W3VdPW1pbihsb3dbdV0sbG93W3ZdKTsKICAgICAgICAgICAgaWYobG93W3ZdPj1kW3VdKQogICAgICAgICAgICAgICAgYXJ0PXRydWU7CiAgICAgICAgfQogICAgfQogICAgaWYoYXJ0JiZwYXJlbnQ+LTEpCiAgICBjdXRwb2ludFt1XT1jaGlsZCsxOwogICAgZWxzZQogICAgY3V0cG9pbnRbdV09MTsKICAgIGlmKHBhcmVudD09LTEmJmNoaWxkPjEpCiAgICBjdXRwb2ludFt1XT1jaGlsZDsKfQoKaW50IG1haW4oKQp7CiAgICBpbnQgbixtLGksYSxiOwogICAgd2hpbGUoY2luPj5uPj5tLG4pCiAgICB7CiAgICAgICAgbWVtc2V0KGxvdywwLHNpemVvZihsb3cpKTsKICAgICAgICBtZW1zZXQoZCwwLHNpemVvZihkKSk7CiAgICAgICAgbWVtc2V0KHZpc2l0ZWQsMCxzaXplb2YodmlzaXRlZCkpOwogICAgICAgIG1lbXNldChjdXRwb2ludCwwLHNpemVvZihjdXRwb2ludCkpOwogICAgICAgIGZvcihpPTA7aTw9bjsrK2kpCiAgICAgICAgR1tpXS5jbGVhcigpOwogICAgICAgIHdoaWxlKGNpbj4+YT4+YixhIT0tMSkKICAgICAgICB7CiAgICAgICAgICAgIEdbYV0ucHVzaF9iYWNrKGIpOwogICAgICAgICAgICBHW2JdLnB1c2hfYmFjayhhKTsKICAgICAgICB9CiAgICAgICAgZHRpbWU9MDsKICAgICAgICBERlMoMCk7CiAgICAgICAgZm9yKGk9MDtpPG47KytpKQogICAgICAgIHsKICAgICAgICAgICAgcmVzdWx0W2ldLmZpcnN0PWk7CiAgICAgICAgICAgIHJlc3VsdFtpXS5zZWNvbmQ9Y3V0cG9pbnRbaV07CiAgICAgICAgfQogICAgICAgIHNvcnQocmVzdWx0LHJlc3VsdCtuLGNvbXBhcmUpOwogICAgICAgIGZvcihpPTA7aTxtOysraSkKICAgICAgICBjb3V0PDxyZXN1bHRbaV0uZmlyc3Q8PCIgIjw8cmVzdWx0W2ldLnNlY29uZDw8ZW5kbDsKICAgICAgICBjb3V0PDxlbmRsOwogICAgfQogICAgcmV0dXJuIDA7Cn0=