Fişierul intrare/ieşire:	hex.in, hex.out	Sursă	ad-hoc
Autor	Catalin Francu	Adăugată de	Catalin Francu •Catalin.Francu
Timp execuţie pe test	0.5 sec	Limită de memorie	4096 kbytes
Scorul tău	N/A	Dificultate	1/5

Pentru aceasta problema accesul la toate sursele trimise este liber!
De asemenea, poti vedea si testele accesand atasamentele.

Vezi solutiile trimise

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 la 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.