// Brute-force search for minimum bipartite vertex cover.
// Enumerates all solutions.

#include <stdio.h>
#include <stdlib.h>

/* Basic bit twiddles */
// Extract bit
#define bitSelect(x,bit) ((x>>(bit))&1)
// Force bit to 1
#define bitSet(x,bit) (x | (1<<(bit)))
// Force bit to 0
#define bitClear(x,bit) (x & ~(1<<(bit)))

int v1,v2,e;
int edge[200][2];

main()
{
int i,j,k,a,b;
int bestSize,bitsOn,cover;

scanf("%d %d %d",&v1,&v2,&e);
if (v1+v2>20)
{
  printf("Too many vertices\n");
  exit(0);
}
if (e>200)
{
  printf("Too many edges\n");
  exit(0);
}
for (i=0;i<e;i++)
{
  scanf("%d %d",&a,&b);
  if (a<0 || a>=v1 || b<v1 || b>=v1+v2)
  {
    printf("bad edge\n");
    exit(0);
  }
  edge[i][0]=a;
  edge[i][1]=b;
}

bestSize=999;
bitsOn=0; // Cardinality of cover
cover=0;  // Initialize cover as empty set
while (!bitSelect(cover,v1+v2))
{
  // Is candidate cover no larger than best cover so far?
  if (bitsOn<=bestSize)
  {
    // Test that every edge i is covered by one of its two vertices
    for (i=0;
         i<e && (bitSelect(cover,edge[i][0]) || bitSelect(cover,edge[i][1]));
         i++)
      ;
    if (i==e) // Success?
    {
      if (bitsOn==bestSize)
        printf("Same size:");
      else
        printf("Size reduced to %d:",bestSize=bitsOn);
      for (i=0;i<v1+v2;i++)
        if (bitSelect(cover,i))
          printf(" %d",i);
      printf("\n");
    }
  }

  // Move on to next candidate by simulating a binary increment
  // First ripple across low-order ones
  for (i=0;
       bitSelect(cover,i);
       i++)
  {
    cover=bitClear(cover,i);
    bitsOn--;
  }

  // Hit the rightmost zero, so change to one
  cover=bitSet(cover,i);
  bitsOn++;
}
}