#include<conio.h>
#include<iostream>
using namespace std;

struct nod{
   int inf;
   nod *adr;
} **ls,*s,*p;


 int n,m,i,j,x,y;
 long e;
 int *match,*tata;
   
void insert(nod *&prim, int v){
   nod *q;
   q=new nod;// se aloca un element al listei
   q->inf=v;
   q->adr=prim;
   prim=q;
}



int extract(nod* &p){
    int x=p->inf;
    nod* q=p;
    p=p->adr;
    delete q;
    return x;
}
    
int main(){
   FILE *f=fopen("cuplaj.in","r");
   FILE *g=fopen("cuplaj.out","w"); 
    
   fscanf(f,"%d",&n);
   fscanf(f,"%d",&m);
   fscanf(f,"%ld",&e);
   ls=new nod*[n+m+1];
    match=new int[n+m];
   tata=new int[n+m];
   int u;
 
       
   for(i=0;i<=n+m;i++){
       match[i]=tata[i]=-1;
       ls[i]=NULL;
   }
   for(i=0;i<e;i++){
      fscanf(f,"%d%d",&x,&y);
      insert(ls[x-1],y+n-1);
      insert(ls[y+n-1],x-1);
   }
   fclose(f);
   s=NULL;
   //culpaj arbitrar-greedy
  
  /* for(i=0;i<n;i++){
       for(nod* p=ls[i];p;p=p->adr)
           if(match[p->inf]==-1){
                match[p->inf]=i;
                match[i]=p->inf;
                break;                
           }
       if(match[i]==-1)
           insert(s,i);//toate vfle nesaturate initial
}   */        


   for(u=0;u<n;u++){
      for(int i=0;i<=n+m;i++)
          tata[i]=-1;
      
        if(match[u]==-1){
           nod* coada=0; 
           insert(coada,u);
           do{
             int x=extract(coada);    
       
             for(p=ls[x];p;p=p->adr){
             if(tata[p->inf]==-1)//nevizitat
                 if(match[p->inf]>=0){// cuplat
                   tata[p->inf]=x;
                   int z=match[p->inf];
                   insert(coada,z);  
                   tata[z]=p->inf;
                 }
                 else
                 if(x!=u){//ex vf nesaturat
                  int y=p->inf;
                  while(x>=0){
                      match[x]=y;
                      match[y]=x;
                      if(tata[x]>=0) match[tata[x]]=-1;
                      y=tata[x];
                      if(y>=0) x=tata[y];
                      else x=-1;
                 }            
               } 
               }
           }while(coada); 
           }    
       }      
       cout<<"final"<<endl<<endl;
       for(int i=0;i<n;i++)
       cout<<match[i]<<" ";
       getch();
       for(int i=0;i<n;i++)
           if(match[i]>=0)
               fprintf(g,"%d %d\n",i+1,match[i]+1-n);               
     fclose(g);
     fclose(f);  
   //getch();
   
  
   return 0;
}