/* Uždavinio autorius: Tomas Laurinavičius, VU MIF studentas;
   Sprendimą bei testus parengė: Dr. Mindaugas Plukas, VU MIF dėstytojas */  

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


/*  
   Uždavinys susiveda į maksimalaus suporavimo dvidaliame grafe radimą.
   Lentos vienetiniai langeliai atitinka grafo viršūnes,o jos sujungtos briaunomis 
   su kaimynais iš viršaus, dešinės, kairės ir apačios. Tada bet koks supjaustymas
   į dviejų vienetinių kvadratėlių dydžio stačiakampius atitinka suporavimą grafe, ir
   atvirkščiai - suporavimas gafe atitinka supjaustymą. Lentą atitinkantis grafas
   yra dvidalis: viršūnės, kurias atitinkančių langelių koordinačių suma yra lyginė,
   sudaro viena dalį( vadinsime ją "lyginę"), likusios - kitą( vadinsime ją "nelyginę").
   
   Maksimalaus suporavimo dvidaliame grafe radimui čia naudojame adaptuotą dvidaliam grafui bazinį 
   Fordo-Fulkersono algoritmą. Turimam suporavimui bandome ieškoti didinančios(alternuojančios)
   grandinės - grandinės, kuri prasidėtų ir baigtusi nesuporuota viršūne, o joje kaitaliotusi briaunos,
   priklausančios ir nepriklausančios turimam suporavimui. Toks kelias yra nelyginio ilgio, jo vienas
   galas yra "lyginė" viršūnė, kitas - "nelyginė". Didinančios grandinės ieškosime pradėdami nuo 
   nesuporuotų lyginių viršūnių vykdydami paiešką platyn. Jei grandinę radome, tai ją pritaikome - 
   grandinės briaunas, kurios priklauso suporavimui, iš suporavimo išmetame, o grandinės briaunas,
   nepriklausančias suporavimui prijungiame prie jo; tokiu būdu gausime naują suporavimą, kuris turės
   viena briauna daugiau. Jei didinančios grandinės turimam suporavimui neegzistuoja, tai jis yra 
   maksimalus ir darbą baigiame.
    
   Tokio algoritmo darbo laikas yra O( (N*M)^2 ). 
 */


#define MAX_LENTOS_DYDIS 50
 
typedef struct _TLangelis 
{
   int fYra ; /* =0, jei langelis išpjautas, 
                 =1, jei langelis yra 
               */
                   
   int porI, porJ ; /* >Šie laukai naudojami įsiminti turimą suporavimą.
                         Jei viršūnė suporuota, tai laukuose saugomos viršūnės porininkės koordinates,
                         jei viršūnė nesuporuota, tai jie lygus (-1) 
                       */
                         
   int isI, isJ;  /* Šie laukai naudojami, ieškant didinančios grandinės, paieškai į plotį realizuoti.
                     Jei ši viršūnė aplankyta, tai:
                        jei ji pradinė paieškos viršūnė, tai laukai lygūs (-2)
                        jei ji nepradinė paieškos viršūnė, tai laukai lygus koordinatėms
                          viršūnės iš kurios į ją atėjom.
                     Jei ši viršūnė nepalankyta, tai laukai lygūs (-2). 
                   */        

} TLangelis ;

typedef TLangelis TLenta[MAX_LENTOS_DYDIS][MAX_LENTOS_DYDIS] ;

int N  = 0 ;   /* Lentos plotis */
int M  = 0 ;   /* Lentos ilgis  */
TLenta lenta ; /* Lenta         */

/* Turimo suporavimo briaunų skaičius */
int supDydis = 0 ;


/* 
   Bando rasti didinančią grandinę ir ją pritaiko
   Jei didinanti grandinė rasta, tai gražina 1, ir gražina 0 priešingu atveju.
 */
int padidink( void ) ;


void main()
{
   FILE *fpDuom = NULL ;
   FILE *fpRez = NULL ;
   int i = 0, j = 0 ;
   int kiekIspj = 0 ;
   int fRadomPadidinima = 0 ; 

/* Nuskaitom plotį, ilgį */
   fpDuom = fopen( "LENTA.DAT", "r" ) ;
   fscanf( fpDuom, " %d ", &N ) ;
   fscanf( fpDuom, " %d ", &M ) ;
   
/* Inicializuojam nesupjaustytą lentą */
   for ( i = 0 ; i < N ; i ++ )
    for ( j = 0 ; j < M ; j ++ )
     {
       lenta[i][j].fYra = 1 ; 
     }
    
/* Nuskaitom išpjautus langelius */
   fscanf( fpDuom, " %d ", &kiekIspj ) ;
   while ( kiekIspj > 0 )
    {
      int ispjI = 0, ispjJ = 0 ;
      fscanf( fpDuom, " %d %d ", &ispjI, &ispjJ ) ;
      lenta[ispjI-1][ispjJ-1].fYra = 0 ;
      kiekIspj -- ;
    }
   fclose( fpDuom ) ; 
    

/* Turim tuščią suporavimą */
   supDydis = 0 ;
   for ( i = 0 ; i < N ; i ++ )
    for ( j = 0 ; j < M ; j ++ )
     {
       lenta[i][j].porI = -1 ; 
       lenta[i][j].porJ = -1 ; 
     }

/* Randam maksimalų suporavimą, ieškodami ir pritaikydami didinančias grandines */
   do {
   
     fRadomPadidinima = padidink() ;
   
    } while ( fRadomPadidinima ) ;


/* Išvedam maksimalaus suporavimo briaunų skaičių */
   fpRez = fopen( "LENTA.REZ", "w" ) ;
   fprintf( fpRez, "%d\n", supDydis ) ;
   fclose( fpRez ) ;

}


/* Viršūnių eilė  */
struct _VirsuniuEilesElementas 
{ 
   int i,j ; 
} virsuniuEile[ MAX_LENTOS_DYDIS * MAX_LENTOS_DYDIS ] ;

int eilPradzia = 0, eilGalas = 0 ;

void VE_istustink( void )
{
   eilPradzia = 0 ;
   eilGalas = 0 ;
}

int VE_tuscia( void )
{
   return eilPradzia >= eilGalas ;
}

void VE_dek( int i, int j )
{
   virsuniuEile[eilGalas].i = i ;
   virsuniuEile[eilGalas].j = j ;
   eilGalas ++ ;
}

void VE_imk( int *pI, int *pJ )
{
   *pI = virsuniuEile[eilPradzia].i ;
   *pJ = virsuniuEile[eilPradzia].j ;
   eilPradzia ++ ;
}
/* Viršūnių eilės apibrėžimo pabaiga */


int padidink( void )
{
   int fRadom = 0 ; /* Ar radom didinančią grandinę */
   int iR = 0, jR = 0 ; /* Didinančios grandinės paskutinė viršūnė */
   int i = 0, j = 0 ;

   /* Išvalom paieškos laukus */
   for ( i = 0 ; i < N ; i ++ )
    for ( j = 0 ; j < M ; j ++ )
     {
       lenta[i][j].isI = -1 ;
       lenta[i][j].isJ = -1 ;
     }

   /* Eilėje saugosime visas aplankytas viršūnes nuo kurių reikia bandyti daryti žingsnį.
      Paiešką pradedam nuo nesuporuotų "lyginių" viršūnių; Jas sudedam į eilę.  
    */ 
   VE_istustink() ;
   for ( i = 0 ; i < N ; i ++ )
    for ( j = 0 ; j < M ; j ++ )
     {
       if ( (i+j) % 2 == 0 && lenta[i][j].fYra ) /* Pradedam nuo "lyginės" dalies neporuotų viršūnių */
        {
          if ( lenta[i][j].porI == -1  ) /* Neporuota virsune */
           {
              VE_dek( i, j ) ;
              lenta[i][j].isI = -2 ;/* Pradinės paieškos viršūnės */  
              lenta[i][j].isJ = -2 ; 
           }
        }
     }
     
   fRadom = 0 ;
   while ( !VE_tuscia() && !fRadom )
    {
      int i = 0, j = 0 ; /* Iš kur darom žingsnį */
      int ii = 0, jj = 0 ; /* Į kur darom žingsnį */
      int fLyginis = 0  ;  /* Ar nagrinėjama viršūnė "lyginė" */
      
      VE_imk( &i, &j ) ;
      fLyginis = ( i + j ) % 2 == 0 ;
      
      if ( ! fLyginis )
       {
         /* Viršūnė "nelyginė". Ji būtinai bus suporuota ir iš jos einame suporavimo briauna 
          */
         ii = lenta[i][j].porI ;
         jj = lenta[i][j].porJ ;
         
         lenta[ii][jj].isI = i ; /* Įsimenam, iš kur atėjom */
         lenta[ii][jj].isJ = j ;
         VE_dek( ii, jj ) ;
         /* Į eilę idėjom "lyginę" viršūnę. Ji yra suporuota, o jos porininkė jau aplankyta */
        }
       else
        { /* Viršūnė "lyginė". Iš jos bandome eiti visomis
             suporavimui nepriklausančiomis briaunomis    
             Nagrinėjama aplankyta "lyginė" viršūnė bus arba nesuporuota( pradinė ),
             arba suporuota ir į ją esame atėję iš jos porininkės. Todėl
             galime tiesiog eiti į visas neaplamkytas viršūnes.
           */
         
          int k = 0 ;
          for ( k = 1 ; k <= 4 ; k ++ )
           {
             /* Bandom eiti į kaimyninę viršūnę */
             switch ( k )
              {
                 case 1 :
                   ii = i ;
                   jj = j + 1 ;
                  break ;
                 case 2 :
                   ii = i + 1 ;
                   jj = j ;
                  break ;
                 case 3 :
                   ii = i ;
                   jj = j - 1 ;
                  break ;
                 case 4 :
                   ii = i - 1 ;
                   jj = j ;
                  break ;
              } ;
              
             /* Patikrinam, ar žingsnis galimas */ 
             if ( ii < 0 || ii >= N || jj < 0 || jj >= M || 
                  ! lenta[ii][jj].fYra ||
                  lenta[ii][jj].isI != -1 /*Jau buvom*/
                )
               continue ;
               
             lenta[ii][jj].isI = i ; /* Įsimenam, iš kur atėjom */
             lenta[ii][jj].isJ = j ;
             
             if ( lenta[ii][jj].porI == -1  ) 
              /* Priėjom "nelyginę" neporuotą viršūnę; reiškia radom didinančią grandinę
                 ir paieškas nutraukiam.
               */
              {
                fRadom = 1 ;
                iR = ii ; jR = jj ;
                break ;
              } 
             else
              {
                VE_dek( ii, jj ) ;
                /* Į eilę idėjom "nelyginė" viršūnę. Ji būtinai bus suporuota */
              } 
           }   
        }
     }
      
   if ( fRadom )
    {
      int i = 0, j = 0 ; /* Iš kur darom žingsnį */
      int ii = 0, jj = 0 ; /* Į kur darom žingsnį */
      int fPoruoti = 0 ;   /* Ar nagrinėjama grandinės briauna įtraukti į suporavimą */

      /* Einam didinančia grandine ir keičiam briaunų suporavimą */
      i = iR ;
      j = jR ;
      fPoruoti = 1 ;
      
      do {
        ii = lenta[i][j].isI ;
        jj = lenta[i][j].isJ ;
        
        if ( fPoruoti )
         {
           lenta[i][j].porI = ii ;
           lenta[i][j].porJ = jj ;
           lenta[ii][jj].porI = i ;
           lenta[ii][jj].porJ = j ;
         }
        
        i = ii ;
        j = jj ;
        fPoruoti = ! fPoruoti ;
      
      } while ( lenta[i][j].isI != -2 ) ;
      
      /* Suporavimas padidėjo viena briauna */
      supDydis ++ ; 
    }
   
   return fRadom ;
}