#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <stack>
#include <set>
#include <stdlib.h>
#include <algorithm>
#include <stack>

using namespace std;

void Reverse_Sort(vector<pair<int, int>>& arr, int l, int r) {
    int i = l, j = r;
    int obj = arr[(l + r) / 2].second;
/* partition */
    while (i <= j) {
        while (arr[i].second > obj)
            i++;
        while (arr[j].second < obj)
            j--;
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    };
/* recursion */
    if (l < j)
        Reverse_Sort(arr, l, j);

    if (i < r)
        Reverse_Sort(arr, i, r);
}



static int a = 1;

vector<pair<int, int>> post(12);

vector<bool> used(12);

void dfs(vector<vector<bool>>& relations,int i){
    bool count = false;
    for(int j=0; j<relations[i].size(); ++j){
        if(relations[i][j]){
            count = true;
            if (!used[j]){
                used[j] = true;
                ++a;
                dfs(relations, j);
            }
        }
    }
    /*if(!count)
        dfs(relations, ++i);*/
    ++a;
    post[i].first=i+1;
    post[i].second=a;
}


vector<vector<std::string>> getList(vector<string>& names, vector<vector<bool>>& relations)
{
    int n = 12;
    dfs(relations, 0);
    Reverse_Sort(post, 0, post.size()-1);
    for(int i=0; i<post.size(); ++i)
        cout<<post[i].first<< "  " << post[i].second<<endl;

    vector<vector<string>> myvector;
    int count = 0;
    for(int i = 0; i < post.size(); ++i ){
        for(int j = 0; j < relations[post[i].first].size(); ++j){
            if(!relations[i][j]) {
                myvector[count].push_back(names[i]);
            }
        }
    }
    int a=3223;
}
int main()
{
    vector<string> names = vector<string>();
    vector<vector<bool>> relations;
    int startIndex;

    ifstream fin;
    fin.open("input.txt");
    if (fin.is_open())
    {
        string str = "";
        getline(fin, str);

        while (str != "#")
        {
            names.emplace_back(str.substr(str.find(' ') + 1));
            getline(fin, str);
        }

        relations = vector<vector<bool>>(names.size());

        for (int i = 0; i < names.size(); i++)
        {
            relations[i] = vector<bool>(names.size());
            for (int j = 0; j < names.size(); j++)
                relations[i][j] = false;
        }

        getline(fin, str);

        while (fin)
        {
            int a = stoi(str.substr(0, str.find(' '))) - 1;
            int b = stoi(str.substr(str.find(' '))) - 1;
            relations[a][b] = true;
            getline(fin, str);
        }

        fin.close();
    }

    vector<vector<string>> res = getList(names, relations);

/*fstream fout;
fout.open("output.txt", ios::out);
for (int i = 0; i < res.size(); i++)
{
for (int j = 0; j < res[i].size(); j++)
fout « res[i][j] « "\n";
fout « "\n";
}
fout.close();*/

    return 0;
}