#include <cstdio>
#include <vector>
#define Nmax 10005
using namespace std;

vector <int> M[Nmax];

int st[Nmax],dr[Nmax],u[Nmax];
int n,m,muchii;

int pair_nod(int poz)
{
    int i;
    if(u[poz]) return 0;
    u[poz]=1;
    for(i=0;i<M[poz].size();i++)
        if(!dr[M[poz][i]])
        {
            st[poz]=M[poz][i];
            dr[M[poz][i]]=poz;
            return 1;
        }
    for(i=0;i<M[poz].size();i++)
        if(pair_nod(dr[M[poz][i]]))
        {
            st[poz]=M[poz][i];
            dr[M[poz][i]]=poz;
            return 1;
        }
    return 0;
}

int main()
{
    int x,y,i,j;
    freopen("cuplaj.in","r",stdin);
    freopen("cuplaj.out","w",stdout);

    scanf("%d%d%d",&n,&m,&muchii);
    for(;muchii;muchii--)
    {
        scanf("%d%d",&x,&y);
        M[x].push_back(y);
    }

    int change=1;
    while(change)
    {
       change=0;
       for(i=1;i<=n;i++) u[i]=0;
       for(i=1;i<=n;i++)
        {
            if(!st[i]) change|=pair_nod(i);
            printf("%d %d\n",i,st[i]);
            for(j=1;j<=n;j++) printf("%d ",st[j]); printf("\n");
            for(j=1;j<=n;j++) printf("%d ",dr[j]); printf("\n\n");
        }
    }

    int cupluri=0;
    for(i=1;i<=n;i++) if(st[i]>0) cupluri++; printf("%d\n",cupluri);
    for(i=1;i<=n;i++) if(st[i]) printf("%d %d\n",i,st[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}