Fișierul intrare/ieșire	hex.in, hex.out	Sursă	ad-hoc
Autor	Cătălin Frâncu	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.15 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	1.75

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Hex

Jocul Hex se joacă pe o tablă de formă romboidală formată din hexagoane, cu latura de N hexagoane (tradițional N = 11). Un jucător are piese roșii, celălalt albastre. Roșul mută primul. Pe rând, jucătorii plasează câte o piesă într-un hexagon. Roșul câștigă dacă face un lanț neîntrerupt de piese care leagă latura stângă de cea dreaptă, iar albastrul câștigă dacă face un lanț neîntrerupt de piese care leagă latura de sus de cea de jos. În exemplul alăturat, ordinea mutărilor a fost A – B – C – D – E – F. La mutarea F, albastrul a câștigat.

Se dau numărul N și N² mutări distincte și corecte. Să se spună după a câta mutare jocul se încheie cu victorie. Se poate demonstra că nu există remize la Hex. (În practică, după mutarea câștigătoare partida se încheie, dar pentru problema de față toate cele N² hexagoane vor fi ocupate).

Date de intrare

Fișierul de intrare hex.in conține pe prima linie numărul N. Pe următoarele N² linii se găsește câte o mutare sub forma L C. Liniile și coloanele sunt numerotate de la 1 al N. Liniile sunt orizontale, iar coloanele oblice de la stânga-sus spre dreapta jos.

Date de ieșire

În fișierul de ieșire hex.out se va tipări un singur număr: numărul primei mutări la care unul dintre jucători închide un lanț câștigător.

Restricții

• 1 ≤ N ≤ 500

Exemplu

Explicație

Vezi imaginea de mai sus.