#include <iostream> 
#include <algorithm> 
#include <string> 
#include <vector> 
using namespace std; 

class V : public vector<int> { 
public: 
    int index; 
    int num, count; 
    V(int idx = 0) :index(idx), num(-1), count(0) { 

    } 
    bool operator < (const V &b) const { 
        if (count != b.count){ 
            return count > b.count; 
        } 
        else{ 
            return index < b.index; 
        } 
    } 
}; 
int dfs(vector<V> &vs, V &v, int c) { 
    v.num = c; 
    int low = c; 
    for (int u : v) { 
        if (vs[u].num < 0) { 
            int t = dfs(vs, vs[u], c + 1); 
            low = min(low, t); 
            if (v.num <= t) v.count++; 
        } else low = min(low, vs[u].num); 
    } 
    return low; 
} 
void solve(int n, int m){ 
    vector<V> vs; 
    for (int i = 0; i < n; i++){ 
        vs.push_back(V(i)); 
    } 
    int x, y; 
    while (cin >> x >> y){ 
        if (x < 0 && y < 0) break; 
        vs[x].push_back(y); 
        vs[y].push_back(x); 
    } 
    for (vector<V>::iterator it = vs.begin(); it != vs.end(); it++){ 
        if ((*it).num < 0){ 
            dfs(vs, *it, 0); 
            if ((*it).count > 0){ 
                (*it).count--; 
            } 
        } 
    } 
    sort(vs.begin(), vs.end()); 
    for (int i = 0; i < m; i++){ 
        cout << vs[i].index << ' ' << vs[i].count + 1 << 'n'; 
    } 
} 
int main(int agrc, char *agrv[]){ 
    ios::sync_with_stdio(false); 
    int n, m; 
    while (cin >> n >> m, n m){ 
        solve(n, m); 
        cout << 'n'; 
    } 
} 

#include <algorithm> 
#include <iostream> 
#include <cstring> 
#include <cstdio> 
using namespace std; 
typedef int ll; 

struct BIT{ 
    ll *vs; 
    int N; 
    BIT(int n){ 
        N = n + 1; 
        vs = new ll[N](); 
    } 
    ~BIT(){ 
        delete[] vs; 
    } 
    void add(int k, ll a){ 
        for (int i = k + 1; i<N; i += i&-i){ 
            vs[i] += a; 
        } 
    } 
    ll sum(int s, int t){ 
        if (s>0) return sum(0, t) - sum(0, s); 
        ll res = 0; 
        for (int i = t; i>0; i -= i&-i) 
            res += vs[i]; 
        return res; 
    } 
}; 
struct Seg{ 
    BIT *dif, *pre; 
    Seg(int n){ 
        dif = new BIT(n); 
        pre = new BIT(n); 
        ll *is = new ll[n]; 
        for (int i = 0; i<n; i++){ 
            cin >> is[i]; 
        } 
        dif->add(0, is[0]); 
        pre->add(0, 0); 
        for (int i = 1; i<n; i++){ 
            ll x = is[i] - is[i - 1]; 
            pre->add(i, x*i); 
            dif->add(i, x); 
        } 
        delete[] is; 
    } 
    ~Seg(){ 
        delete dif; 
        delete pre; 
    } 
    void update(int s, int t, ll v){ 
        dif->add(s, v); 
        dif->add(t, -v); 
        pre->add(s, v*s); 
        pre->add(t, -v*t); 
    } 
    ll query(int s, int t){ 
        if (s>0) return query(0, t) - query(0, s); 
        ll ps = pre->sum(0, t); 
        ll ds = dif->sum(0, t); 
        return ds*t - ps; 
    } 
}; 
void solve(int n, int m, int q){ 
    Seg seg(n); 
    int l = 0; 
    for (int i = 0; i < q; i++){ 
        int query; 
        cin >> query; 
        l = query - 1; 
        cout << seg.query(l, l + m) << 'n'; 
        seg.update(l, l + m, -1); 
    } 
} 
int main(int agrc, char *agrv[]) { 
    int n, m, q; 
    while (cin >> n >> m >> q){ 
        solve(n, m, q); 
    } 
} 

#include <iostream> 
#include <vector> 
#include <sstream> 
#include <string> 
#include <algorithm> 
#include <cstring> 
using namespace std; 
struct info{ 
    int len; 
    int dclock; 
    int *cut; 
    int *low; 
    int *dfn; 
    info(int n){ 
        len = n; 
        dclock = 1; 
        cut = new int[n]; 
        low = new int[n]; 
        dfn = new int[n]; 
        memset(cut, 0, sizeof(int)*len); 
        memset(dfn, -1, sizeof(int)*len); 
    } 
    ~info(){ 
        delete[] cut; 
        delete[] low; 
        delete[] dfn; 
    } 
}; 
void dfs(info &tree, vector< vector<int> > &map, int u, int fa){ 
    int son = 0; 
    tree.dfn[u] = tree.low[u] = tree.dclock++; 
    for (int i = 0; i < map[u].size(); i++){ 
        int v = map[u][i]; 
        if (tree.dfn[v]<0){ 
            dfs(tree, map, v, u); 
            son++; 
            tree.low[u] = min(tree.low[u], tree.low[v]); 
            if ((fa < 0 && son > 1) (fa >= 0 && tree.low[v] >= tree.dfn[u])) 
                tree.cut[u] = 1; 
        } 
        else if (tree.low[u] > tree.low[v] && v != fa){ 
            tree.low[u] = min(tree.low[u], tree.dfn[v]); 
        } 
    } 
} 
int solve(int n){ 
    vector<vector<int>> map; 
    map.resize(n); 
    int s, u; 
    while (1){ 
        string temp; 
        getline(cin, temp); 
        istringstream buf(temp); 
        buf >> s; 
        if (s == 0) break; 
        while (buf >> u){ 
            map[s - 1].push_back(u - 1); 
            map[u - 1].push_back(s - 1); 
        } 
    } 
    info tree(n); 
    for (int i = 0; i < n; i++){ 
        if (map[i].size()>0){ 
            dfs(tree, map, i, -1); 
            break; 
        } 
    } 
    int cnt = 0; 
    for (int i = 0; i < n; i++){ 
        if (tree.cut[i] == 1) 
            cnt++; 
    } 
    return cnt; 
} 

int main(int agrc, char *agrv[]){ 
    int n; 
    while (cin >> n, n){ 
        cout << solve(n) << endl; 
    } 
}