Kao odmor od kvalifikacija, odlučili ste da uzmete tablu sa ~N~ redova (numerisanih od 1 do ~N~) i ~M~ kolona (numerisanih od 1 do ~M~) , i da je obojite u razne boje. Neka polja na tabli su već bila crna, pa ste odlučili da obojite ostala polja tako da važi sledeće:

• nijedno polje ne obojite u crno,
• susedna polja obojite istom bojom (polja su susedna ako dele ivicu, tako da jedno polje može imati najviše četiri suseda), i
• tabla sadrži što više različitih boja.

Vaš zadatak je da odredite koliko će vam različitih boja (ne računajući crnu) biti potrebno da obojite tablu.

Opis ulaza

U prvoj liniji standardnog ulaza nalaze se tri broja ~N~, ~M~ i ~K~, gde su ~N~ i ~M~ redom broj redova i kolona table, a ~K~ je broj crnih polja.

U narednih ~K~ redova nalaze se po dva broja ~A_i~ i ~B_i~, koji predstavljaju red i kolonu ~i~-tog crnog polja.

Opis izlaza

U prvu i jedinu liniju standardnog izlaza ispisati jedan broj: broj boja potrebnih da bi se tabla obojila u skladu sa datim uslovima.

Primer 1

Ulaz

4 4 5
1 1
2 2
3 3
4 4
1 3

Izlaz

3

Primer 2

Ulaz

2 4 2
2 2
2 4

Izlaz

1

Objašnjenje primera

Jedan primer bojenja table date u prvom primeru se može videti na sledećoj slici.

U drugom primeru, jedini način da se zadovolje svi uslovi je da se sva polja koja nisu crna oboje istom bojom.

Ograničenja

• ~1 \leq A_i \leq N~ i ~1 \leq B_i \leq M~.
• ~0 \leq K \leq 100000~.
• Postoji barem jedno belo polje.

Test primeri su podeljeni u 4 disjunktne grupe:

• U test primerima vrednim 20 poena, ~N, M \leq 10~.
• U test primerima vrednim 20 poena, ~N, M \leq 1000~.
• U test primerima vrednim 20 poena, ~N, M \leq 10^9~ i ~K \leq 3000~.
• U test primerima vrednim 40 poena, ~N, M \leq 10^9~.