ad

#include <bits/stdc++.h>
#define inf (1 << 29)
using namespace std;

vector<vector<int> > grafo(80000);

vector<int> BFS(int &nodos, int inicio)
{
    vector<int> distancias(grafo[inicio].size(), inf);
    queue<int> colita;

    colita.push(inicio);
    distancias[inicio]=0;

    while(colita.size())
    {
        int nodo=colita.front();
        colita.pop();
        for(int i=0; i<grafo[nodo].size(); i++)
        {
            int vecino=grafo[nodo][i];
            if(distancias[nodo]+1<distancias[vecino])
                distancias[vecino]=distancias[nodo]+1;
        }
    }

    return distancias;
}

int main()
{
    int pares;
    cin >> pares;

    string pais;
    map<string, int> id;
    vector<string> nombres(80000);

    for(int i=0; i<pares; i++)
    {
        int a, b;

        cin >> pais;
        if(id[pais]==0)
            id[pais]=id.size();

        a=id[pais];
        nombres[i+1]=pais;

        cin >> pais;
        if(id[pais]==0)
            id[pais]=id.size();

        b=id[pais];
        nombres[i+1]=pais;

        grafo[a].push_back(b);
        grafo[b].push_back(a);
    }

    int nodos=id.size()+1;
    map<string, int>::iterator it=id.begin();
    grafo.resize(nodos);
    nombres.resize(nodos);
    sort(nombres.begin(), nombres.end());

    for(int i=1; i<nodos; i++)
    {
        cout << it->first << " " << grafo[it->second].size() << endl;
        it++;
    }

    for(int i=1; i<nodos; i++)
    {
        vector<int> limitrofes=BFS(nodos, i);
        for(int j=0; j<grafo[i].size(); j++)
        {
            if(limitrofes[j]>100000)
                cout << nombres[i] << " " << nombres[j] << endl;
        }
    }

    return 0;
}