Hogy pihenjetek egy kicsit a kvalifikációs feladatok megoldása közben, elhatároztátok, hogy magatok elé vesztek egy táblát \(N\) sorral (a sorok számozása 1-től \(N\)-ig megy) és \(M\) oszloppal (az oszlopok sorszámozása 1-től \(M\)-ig megy), hogy kiszínezzétek különböző színűre. Egyes mezők már feketék a táblán ezért elhatároztátok, hogy kiszínezitek a többi mezőt a következő feltételek betartásával:

• egy mezőt se színeztek feketére,
• a szomszédos mezőket azonos színűre színezitek (a mezők akkor szomszédosak, ha közös az élük, vagyis egy mezőnek legfeljebb négy szomszédja lehet), és
• a tábla minél több különböző színt kapjon.

A feladatotok az, hogy meghatározzátok, hányféle színre lesz szükségetek, hogy a táblát kiszínezzétek. A feketét nem számoljuk.

Bemenet

A szabványos bemenet első sorában három szám van: \(N\), \(M\) és \(K\). Az \(N\) és \(M\) sorban a tábla sorainak és oszlopainak számát jelenti, a \(K\) pedig a fekete mezők számát adja meg.

A következő \(K\) sor mindegyikében két szám: \(A_i\) és \(B_i\) található, amelyek az \(i\)-edik fekete mező sorát és oszlopát definiálják.

Kimenet

A szabványos kimenet első, és egyetlen sorában egy számot íratni ki: a színek számát, amellyel a táblát kiszínezheted az adott feltételek betartásával.

1. példa

Bemenet

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

Kimenet

3

2. példa

Bemenet

2 4 2
2 2
2 4

Kimenet

1

A példa magyarázata

Az 1. példa magyarázata a következő képen látható.

A 2. példa esetében az egyetlen lehetőség az, ha minden nem fekete mezőt azonos színűre színezünk.

Korlátozások

• \(1 \leq A_i \leq N\) és \(1 \leq B_i \leq M\).
• \(0 \leq K \leq 100000\).
• Létezik legalább egy fehér mező.

A tesztpéldák 4 független csoportba oszthatók:

• Tesztpéldák, melyek 20 pontot érnek: \(N, M \leq 10\).
• Tesztpéldák, melyek 20 pontot érnek: \(N, M \leq 1000\).
• Tesztpéldák, melyek 20 pontot érnek: \(N, M \leq 10^9\) és \(K \leq 3000\).
• Tesztpéldák, melyek 40 pontot érnek: \(N, M \leq 10^9\).