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