#include <iostream.h>

#define MAX 128
#define FALSE 0
#define TRUE  1

typedef char BOOL;

BOOL a[MAX][MAX];   // Matice sousednosti
unsigned N;         // Počet vrcholů

unsigned outPoint(unsigned k)
// Hledá město v nějakém výstupním okrese, do kterého je možné se dostat z okresu,
// ve kterém leží město k
{
   for(unsigned i=0; i<N; i++)
      if( a[k][i] && !a[i][k]) k=i;
   return k;
}

unsigned inPoint(unsigned k)
// Hledá město v nějakém vstupním okrese, ze kterého je možné se dostat do okresu,
// ve kterém leží město k
{
   for(unsigned i=0; i<N; i++)
      if(!a[k][i] &&  a[i][k]) k=i; 
   return k;
}

void addEdge(unsigned k, unsigned l)
// Přidá silnici z města k do města l a patřičně opraví matici
{
   cout << k << " " << l << "\n";
   for(unsigned i=0; i<N; i++)
      for(unsigned j=0; j<N; j++)
         if(a[i][k] && a[l][j]) a[i][j]=TRUE;
}

void main() 
{ 
   unsigned i, j, k, l;
   BOOL change;

   cout << "Pocet mest: ";
   cin >> N;

   for(i=0; i<N; i++)
      for(j=0; j<N; j++) a[i][j]=(i==j);

   cout << "Silnice (vstup se ukončí 0 0):\n";
   for(;;) {
      cin >> i >> j;
      if(!i && !j) break;
      a[i][j]=TRUE;
   }

   // Tranzitivní uzávěr
   do {
      change=FALSE;
      for(i=0; i<N; i++)
         for(j=0; j<N; j++)
            for(k=0; k<N; k++)
               if(a[i][j] && a[j][k] && !a[i][k])
                  a[i][k]=change=TRUE;
   } while(change);

   // Nejdříve přidávej silnice, které nevytvoří cykly
   cout << "Je treba jeste vybudovat:\n";
   for(i=0; i<N; i++)
      for(j=0; j<N; j++)   
         if(!a[k=outPoint(j)][l=inPoint(i)])
            if(!a[l][k])
               addEdge(k,l);

   // Pak přidej ostatní
   for(i=0; i<N; i++)
      for(j=0; j<N; j++)
         if(!a[k=outPoint(j)][l=inPoint(i)])
            addEdge(k,l);
}