În camera copiilor problema spațiului este esențială. De aceea locul unde sunt depozitate jucăriile este asemănător unei matrici pătratice, dispuse vertical, fiecare jucărie ocupând un locație bine stabilită.

Entuziasmul și bucuria copiilor în a se juca este bine cunoscută, dar și ”disponibilitatea” acestora de a ordona (reașeza) jucăriile la locul prestabilit este proverbială. Cum, după o rundă de joacă, întotdeauna urmează un episod din serialul de desene animate preferat, copii așează la întâmplare jucăriile.

Cunoscând numărul M de jucării, iar pentru fiecare jucărie locația în care copii au pus jucăria (linie, coloană), precum și locația unde trebuie corect pusă aceasta (linie, coloană), ajutați bona să reașeze jucăriile astfel încât numărul de mutării să fie minim. În cazul în care locația unde trebuie mutată o jucărie este ocupată, atunci bona depozitează temporar jucăria într-o locație specială, dacă este liberă, până când locația unde trebuie mutată se va elibera.

Cerința

Să se determine:

• numărul minim de mutări ce nu necesită folosirea locației speciale
• numărul minim de mutări necesar rearanjării tuturor jucăriilor

Date de intrare

Fișierul de intrare bona.in conține pe prima linie două numere naturale N, M ce reprezintă în ordine, numărul de linii și coloane ale dulapului/matrice folosit pentru jucării, respectiv numărul de jucării.

Pe următoarele M linii un set de patru numere naturale ce reprezintă locația inițială (linia, coloana), respectiv locația finală (linia, coloana) pentru fiecare jucărie.

Date de ieșire

Fișierul de ieșire bona.out va conține pe prima linie o valoare ce reprezintă numărul minim de mutării ce nu necesită folosirea locației speciale, iar pe a doua linie numărul minim de mutări necesar rearanjării tuturor jucăriilor.

Restricții și precizări

• 1 ≤ N ≤ 1000
• 1 ≤ M ≤ 10000
• locațiile inițiale sunt distincte între ele, locațiile finale sunt distincte între ele
• două jucării nu pot ocupa în același timp aceeași locație.
• rezolvarea primei cerințe asigură 30% din punctajul unui test
• pentru datele de intrare se asigură existența unei soluții

Exemplu:

bona.in

4 5
1 1 3 4
3 4 1 1
3 1 4 3
1 2 2 4 
2 4 1 2   

bona.out

3
7

Explicație

Jucăria 1 trebuie mutată din locația (1,1) în locația (3,4), dar aceasta este ocupată. Bona mută jucăria în locația specială. Jucăria 2 se mută din (3,4) în (1,1), eliberând locația (3,4). Jucăria 1 se mută din locația specială în locația finală (3,4).

Jucăria 3 se mută din (3,1) în (4,3). Jucăria 4 trebuie mutată din locația (1,2) în locația (2,4), dar aceasta este ocupată. Jucăria 4 este mutată de bonă în locația specială.

Jucăria 5 se mută din (2,4) în (1,2). Jucăria 4 se mută din locația specială în locația finală (2,4).