UVA 10459

#define ll long long
#include <bits/stdc++.h>
using namespace std;

/*
Ordered set usage:
order_of_key (k) : Number of items strictly smaller than k.
find_by_order(k) : K-th element in a set (counting from zero).
*/

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int OO = 1e9;
const double EPS = 1e-9;

int head[5000], nxt[10000], edge[10000], deg[5000], rem[5000];
vector<int> worst,best;
int best_h = 1e9;
int worst_h = 0;
int g_sz = 0;

void add_edge(int a, int b) {
    edge[g_sz] = b;
    nxt[g_sz] = head[a];
    head[a] = g_sz;
    deg[a]++;
    g_sz++;
}

void dfs(int x, int parent, int dist, int t_dist) {
    int e_idx = head[x];
    bool is_leaf = true;
    while(e_idx != -1) {
        int e = edge[e_idx];
        if(e != parent) {
            dfs(e,x,dist+1,t_dist);
            is_leaf = false;
        }
        e_idx = nxt[e_idx];
    }
    if(is_leaf && dist == t_dist) {
        worst.push_back(x);
    }
}


int get_h(int x, int parent) {
    int ret = 0;
    int e_idx = head[x];
    while(e_idx != -1) {
        int e = edge[e_idx];
        if(e != parent) {
            ret = max(ret,get_h(e,x));
        }
        e_idx = nxt[e_idx];
    }
    return ret+1;
}

void rw_add(int r) {
    vector<pair<int,int>> v;
    int e_idx = head[r];
    while(e_idx != -1) {
        int e = edge[e_idx];
        v.push_back({get_h(e,r),e});
        e_idx = nxt[e_idx];
    }
    sort(v.begin(), v.end());
    for(int i = ((int)v.size())-1; i >= 0; i--) {
        if(v.size() < 2 || v[i].first >= v[v.size()-2].first) {
            //cout << "here at v[i].second = " << v[i].second << "\n";
            dfs(v[i].second,r,1,v[i].first);
        }

    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    //freopen("out.txt","w",stdout);
    int n;
    while(cin >> n) {
        g_sz = 0;
        worst.clear();
        best.clear();
        //best_h = 1e9;
        //worst_h = 0;
        for(int i = 0; i < n; i++) {
            head[i] = -1;
            deg[i] = 0;
            rem[i] = 0;
        }
        for(int i = 0; i < n; i++) {
            int k;
            cin >> k;
            for(int j = 0; j < k; j++) {
                int b;
                cin >> b;
                b--;
                add_edge(i,b);
            }
        }
        /*for(int i = 0; i < n; i++) {
            int h = get_h(i,-1);
            if(h < best_h) {
                best_h = h;
                best.clear();
            }
            if(h == best_h) {
                best.push_back(i);
            }
            if(h > worst_h) {
                worst_h = h;
                worst.clear();
            }
            if(h == worst_h) {
                worst.push_back(i);
            }
        }*/
        queue<int> curr;
        queue<int> prv;
        for(int i = 0; i < n; i++) {
            if(deg[i] == 1) {
                curr.push(i);
            }
        }
        while(!curr.empty()) {
            int c_sz = curr.size();
            while(!prv.empty()) {
                prv.pop();
            }
            for(int i = 0; i < c_sz; i++) {
                int x = curr.front();
                //cout << "removing " << x+1 << " from curr " << "\n";
                curr.pop();
                prv.push(x);
                rem[x] = 1;
                int c_idx = head[x];
                while(c_idx != -1) {
                    int c = edge[c_idx];
                    deg[c]--;
                    if(!rem[c] && deg[c] == 1) {
                        curr.push(c);
                    }
                    c_idx = nxt[c_idx];
                }
            }
        }
        //vector<int> best;
        while(!prv.empty()) {
            best.push_back(prv.front());
            prv.pop();
        }
        //dfs(best[0],-1);
        for(int r : best) {
            rw_add(r);
        }
        sort(best.begin(),best.end());
        sort(worst.begin(),worst.end());
        cout << "Best Roots  : ";
        for(int i = 0; i < best.size(); i++) {
            if(i)
                cout << " ";
            cout << best[i]+1;
        }
        cout << "\nWorst Roots : ";
        for(int i = 0; i < worst.size(); i++) {
            if(i && worst[i] == worst[i-1])
                continue;
            if(i)
                cout << " ";
            cout << worst[i]+1;
        }
        cout << "\n";
    }
    return 0;
}