#include "bits/stdc++.h"
using namespace std;
////////////// Prewritten code follows. Look down for solution. ////////////////
#define fs first
#define sc second
#define pb push_back
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend
#define forn(i, n) for(int i = 0; i < (int)(n); ++i)
#define for1(i, n) for(int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for(int i = (int)(n); i >= 0; --i)
#define fore(i, a, b) for(int i = (int)(a); i <= (int)(b); ++i)
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vll;
template<typename T> void maxself(T &a, T &b){a = max(a, b);};
template<typename T> void minself(T &a, T &b){a = min(a, b);};
const ll LINF = 1e18;
const int INF = 1e9;
const int MOD = 1e9+7;
/// command for char arrays with spaces -> scanf(" %[^\n]", text);
////////////////////////// Solution starts below. //////////////////////////////
const int N = 1e4+5;
vvi adj;
vi dfsChildren, dfsNum, dfsLow, dfsParent;
bitset<N> artV;
int dfsTime, root, rootChildren;
void init(int n){
adj.clear();
adj.resize(n);
dfsNum.clear();
dfsNum.resize(n, 0);
dfsLow.clear();
dfsLow.resize(n, 0);
dfsParent.clear();
dfsParent.resize(n, 0);
dfsChildren.clear();
dfsChildren.resize(n, 0);
artV.reset();
}
bool comp(int &a, int &b){
if(dfsChildren[a] == dfsChildren[b]){
return a < b;
}
return dfsChildren[a] > dfsChildren[b];
}
void dfs(int v){
dfsNum[v] = dfsLow[v] = dfsTime++;
for(int u : adj[v]){
if(!dfsNum[u]){
dfsParent[u] = v;
dfsChildren[v]++;
if(v == root) rootChildren++;
dfs(u);
if(u != root and dfsLow[u] >= dfsNum[v]){
artV[v] = 1;
}
minself(dfsLow[v], dfsLow[u]);
}else if(u != dfsParent[v]){
minself(dfsLow[v], dfsNum[u]);
}
}
}
int main(){
int n, m;
while(scanf("%d %d", &n, &m), n || m){
init(n);
int a, b;
while(true){
scanf("%d %d", &a, &b);
if(a < 0 and b < 0) break;
adj[a].pb(b);
adj[b].pb(a);
}
dfsTime = 1;
forn(i, n){
if(!dfsNum[i]){
root = i;
rootChildren = 0;
dfs(root);
if(rootChildren > 1){
artV[root] = 1;
}
}
}
vector<int> ans;
forn(i, n){
if(artV[i])
ans.pb(i);
}
if(len(ans) < m){
forn(i, n){
if(!artV[i]) ans.pb(i);
if(len(ans) == m) break;
}
}
sort(all(ans), comp);
for(int v : ans){
printf("%d %d\n", v, dfsChildren[v]);
}
}
return 0;
}
I2luY2x1ZGUgImJpdHMvc3RkYysrLmgiCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKLy8vLy8vLy8vLy8vLy8gUHJld3JpdHRlbiBjb2RlIGZvbGxvd3MuIExvb2sgZG93biBmb3Igc29sdXRpb24uIC8vLy8vLy8vLy8vLy8vLy8KCiNkZWZpbmUgZnMgZmlyc3QKI2RlZmluZSBzYyBzZWNvbmQKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBsZW4oeCkgKChpbnQpKHgpLnNpemUoKSkKI2RlZmluZSBhbGwoeCkgKHgpLmJlZ2luKCksICh4KS5lbmQoKQojZGVmaW5lIHJhbGwoeCkgKHgpLnJiZWdpbigpLCAoeCkucmVuZAojZGVmaW5lIGZvcm4oaSwgbikgZm9yKGludCBpID0gMDsgaSA8IChpbnQpKG4pOyArK2kpCiNkZWZpbmUgZm9yMShpLCBuKSBmb3IoaW50IGkgPSAxOyBpIDw9IChpbnQpKG4pOyArK2kpCiNkZWZpbmUgZm9yZChpLCBuKSBmb3IoaW50IGkgPSAoaW50KShuKTsgaSA+PSAwOyAtLWkpCiNkZWZpbmUgZm9yZShpLCBhLCBiKSBmb3IoaW50IGkgPSAoaW50KShhKTsgaSA8PSAoaW50KShiKTsgKytpKQoKdHlwZWRlZiBwYWlyPGludCwgaW50PiBwaWk7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgdmVjdG9yPHBpaT4gdnBpOwp0eXBlZGVmIHZlY3Rvcjx2aT4gdnZpOwp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiBwYWlyPGxsLCBsbD4gcGxsOwp0eXBlZGVmIHZlY3RvcjxsbD4gdmw7CnR5cGVkZWYgdmVjdG9yPHZsPiB2bGw7Cgp0ZW1wbGF0ZTx0eXBlbmFtZSBUPiB2b2lkIG1heHNlbGYoVCAmYSwgVCAmYil7YSA9IG1heChhLCBiKTt9Owp0ZW1wbGF0ZTx0eXBlbmFtZSBUPiB2b2lkIG1pbnNlbGYoVCAmYSwgVCAmYil7YSA9IG1pbihhLCBiKTt9OwoKY29uc3QgbGwgTElORiA9IDFlMTg7CmNvbnN0IGludCBJTkYgPSAxZTk7CmNvbnN0IGludCBNT0QgPSAxZTkrNzsKCi8vLyBjb21tYW5kIGZvciBjaGFyIGFycmF5cyB3aXRoIHNwYWNlcyAtPiBzY2FuZigiICVbXlxuXSIsIHRleHQpOwogCi8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vIFNvbHV0aW9uIHN0YXJ0cyBiZWxvdy4gLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vCgpjb25zdCBpbnQgTiA9IDFlNCs1Owp2dmkgYWRqOwp2aSBkZnNDaGlsZHJlbiwgZGZzTnVtLCBkZnNMb3csIGRmc1BhcmVudDsKYml0c2V0PE4+IGFydFY7CmludCBkZnNUaW1lLCByb290LCByb290Q2hpbGRyZW47Cgp2b2lkIGluaXQoaW50IG4pewoJYWRqLmNsZWFyKCk7CglhZGoucmVzaXplKG4pOwoJZGZzTnVtLmNsZWFyKCk7CglkZnNOdW0ucmVzaXplKG4sIDApOwoJZGZzTG93LmNsZWFyKCk7CglkZnNMb3cucmVzaXplKG4sIDApOwoJZGZzUGFyZW50LmNsZWFyKCk7CglkZnNQYXJlbnQucmVzaXplKG4sIDApOwoJZGZzQ2hpbGRyZW4uY2xlYXIoKTsKCWRmc0NoaWxkcmVuLnJlc2l6ZShuLCAwKTsKCWFydFYucmVzZXQoKTsKfQoKYm9vbCBjb21wKGludCAmYSwgaW50ICZiKXsKCWlmKGRmc0NoaWxkcmVuW2FdID09IGRmc0NoaWxkcmVuW2JdKXsKCQlyZXR1cm4gYSA8IGI7Cgl9CglyZXR1cm4gZGZzQ2hpbGRyZW5bYV0gPiBkZnNDaGlsZHJlbltiXTsKfQoKdm9pZCBkZnMoaW50IHYpewoJZGZzTnVtW3ZdID0gZGZzTG93W3ZdID0gZGZzVGltZSsrOwoJZm9yKGludCB1IDogYWRqW3ZdKXsKCQlpZighZGZzTnVtW3VdKXsKCQkJZGZzUGFyZW50W3VdID0gdjsKCQkJZGZzQ2hpbGRyZW5bdl0rKzsKCQkJaWYodiA9PSByb290KSByb290Q2hpbGRyZW4rKzsKCQkJZGZzKHUpOwoJCQlpZih1ICE9IHJvb3QgYW5kIGRmc0xvd1t1XSA+PSBkZnNOdW1bdl0pewoJCQkJYXJ0Vlt2XSA9IDE7CgkJCX0KCQkJbWluc2VsZihkZnNMb3dbdl0sIGRmc0xvd1t1XSk7CgkJfWVsc2UgaWYodSAhPSBkZnNQYXJlbnRbdl0pewoJCQltaW5zZWxmKGRmc0xvd1t2XSwgZGZzTnVtW3VdKTsKCQl9Cgl9Cn0KCmludCBtYWluKCl7CgoJaW50IG4sIG07Cgl3aGlsZShzY2FuZigiJWQgJWQiLCAmbiwgJm0pLCBuIHx8IG0pewoJCWluaXQobik7CgkJaW50IGEsIGI7CgkJd2hpbGUodHJ1ZSl7CgkJCXNjYW5mKCIlZCAlZCIsICZhLCAmYik7CgkJCWlmKGEgPCAwIGFuZCBiIDwgMCkgYnJlYWs7CgkJCWFkalthXS5wYihiKTsKCQkJYWRqW2JdLnBiKGEpOwoJCX0KCQlkZnNUaW1lID0gMTsKCQlmb3JuKGksIG4pewoJCQlpZighZGZzTnVtW2ldKXsKCQkJCXJvb3QgPSBpOwoJCQkJcm9vdENoaWxkcmVuID0gMDsKCQkJCWRmcyhyb290KTsKCQkJCWlmKHJvb3RDaGlsZHJlbiA+IDEpewoJCQkJCWFydFZbcm9vdF0gPSAxOwoJCQkJfQoJCQl9CgkJfQoJCXZlY3RvcjxpbnQ+IGFuczsKCQlmb3JuKGksIG4pewoJCQlpZihhcnRWW2ldKQoJCQkJYW5zLnBiKGkpOwoJCX0KCQlpZihsZW4oYW5zKSA8IG0pewoJCQlmb3JuKGksIG4pewoJCQkJaWYoIWFydFZbaV0pIGFucy5wYihpKTsKCQkJCWlmKGxlbihhbnMpID09IG0pIGJyZWFrOwoJCQl9CgkJfQoJCXNvcnQoYWxsKGFucyksIGNvbXApOwoJCWZvcihpbnQgdiA6IGFucyl7CgkJCXByaW50ZigiJWQgJWRcbiIsIHYsIGRmc0NoaWxkcmVuW3ZdKTsKCQl9Cgl9CgkKCXJldHVybiAwOwp9