nakhla

Enunț

Nargy şi Fumeanu joacă un joc numit Nakhla. Acesta se joacă cu jetoane pe o tablă de lungime $N$ şi lăţime $M$.

Jetoanele lui Nargy sunt de culoare albă, iar ale lui Fumeanu de culoare neagră. La începutul jocului, fiecare jucător are câte $N$ jetoane pe care le amplasează câte unul pe un rând, cu condiţia ca pe fiecare rând jetonul de culoare albă să fie la stânga jetonului de culoare neagră.

După amplasarea jetoanelor, cei doi jucători fac câte o mutare alternativ, prima mutare fiind făcută de jucătorul cu jetoanele albe. O mutare constă în deplasarea unui jeton astfel: Nargy va alege un jeton de culoare albă şi îl va muta la dreapta; Fumeanu va alege un jeton de culoare neagră şi îl va muta la stânga. O mutare poate fi efectuată doar dacă se respectă în continuare condiţia ca pe fiecare rând jetonul de culoare albă să fie la stânga jetonului de culoare neagră. Jocul se termină când nu se mai poate efectua nici o mutare, iar jucătorul care a făcut ultima mutare este câştigător.

Cerință

Scrieţi un program care joacă jocul Nakhla în rolul lui Nargy, împotriva lui Fumeanu.

Protocol de interacţiune

Programul vostru nu va efectua operaţii cu niciun fişier. El va trebui să implementeze funcția

void solve(int N, int M, std::vector<std::pair<int, int>> moves);

unde vectorul moves conține $N$ perechi de numere întregi $A_i \ B_i\ (A_i < B_i)$ cu semnificaţia că Nargy a plasat o piesă pe linia $i$ şi coloana $A_i$, iar Fumeanu o piesă pe linia $i$ şi coloana $B_i$.

Apoi, pentru a juca împotriva comisiei va trebui să apelați funcția

std::pair<int, int> move(int i, int j);

unde parametrii $i \ j$ cu $i \ (1 \leq i \leq N)$ reprezintă linia pe care se face mutarea iar $j \ (j > 0)$ numărul de coloane cu care se va muta jetonul la dreapta. Funcța va returna o pereche de alte numere $i \ j$ reprezentând mutarea lui Fumeanu. Numărul $i \ (1 \leq i \leq N)$ reprezintă linia pe care se face mutarea, iar $j \ (j > 0)$ numărul de coloane cu care se va muta jetonul la stânga.

În momentul în care nu se mai poate face nici o mutare programul își va termina execuţia, indiferent de jucătorul care a facut ultima mutare.

Exemplu

Se apelează solve(3, 6, {{1,3},{2,5},{1,6}}) de către comisie
Concurentul apelează move(3, 1) (mutarea lui Nargy), care returnează {3, 3} (mutarea lui Fumeanu)
Concurentul apelează move(2, 1) (mutarea lui Nargy), care returnează {2, 1} (mutarea lui Fumeanu)
Concurentul apelează move(1, 1) (mutarea lui Nargy).
Jocul s-a terminat, se oprește execuția programului.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$;
• $1 \leq M < 2^{31}$;
• În nici un moment nu pot exista două jetoane în aceeaşi locaţie pe tablă;
• Dacă programul vostru joacă optim, se garantează că pentru orice test Nargy va avea întotdeauna strategie de câştig.;
• Dacă programul vostru joacă optim, se garantează că programul comisiei va juca astfel încât jocul să se termine în cel mult
  $150 \ 000$ de mutări. Dacă programul vostru depăşeşte acest număr de mutări nu se va acorda niciun punct.