Fişierul intrare/ieşire:	ture-impiedicate.in, ture-impiedicate.out	Sursă	ad-hoc
Autor		Adăugată de	Livia Magureanu •livlivi
Timp execuţie pe test	0.4 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Ture Impiedicate

Miruna învaţă şah. Ea a ajuns la piesa tură şi a înţeles că aceasta se poate deplasa doar pe orizontală sau pe verticală. De asemenea, ştie deja că dacă o altă piesă se află în calea unei ture aceasta poate fi atacată.
Miruna i s-a părut că este prea simplă teoria mutării unei ture şi şi-a imaginat următoarea problemă:
Pe o tablă de şah N * N ea aşază la întâmplare K ture. Nu poate pune 2 ture în aceeaşi căsuţă (poziţie pe tablă). Ea doreşte să mute turele astfel încât, la finalul mutărilor, nicio tură să nu poată ataca altă tură.
După mai multe încercări fetiţa şi-a propus să determine numărul minim de mutări necesare pentru a obţine aşezarea finală a turelor.
Întrucât turele Mirunei sunt mai vechi şi cam împiedicate, ele se pot deplasa doar cu câte o căsuţă (la stânga, dreapta, în sus sau în jos) la fiecare mutare. O tură nu poate sări peste o altă tură şi nici nu poate părăsi tabla de şah.

Date de intrare

În fişierul de intrare ture-impiedicate.in, prima linie va conţine valorile N şi K cu semnificaţia din enunţ.
Pe următoarele K linii se vor afla câte 2 valori, l_i şi c_i, separate printr-un spaţiu, care reprezintă linia şi, respectiv, coloana la care se află tura iniţial.

Date de ieşire

În fişierul de ieşire ture-impiedicate.out, pe prima linie, se va afişa numărul minim de mutări (valide) pentru a obţine o configuraţie în care nicio tură nu poate ataca o altă tură.

Restricţii

• K ≤ N
• 1 ≤ c_i, l_i ≤ N oricare ar fi i din {1, 2, ..., K}

Subtaskuri

Exemplu

Cum se trimit solutii?