Lui Vasilica ii plac la nebunie jocurile de carti, dar, fiindca are doar 4
ani, pierde de fiecare data cand joaca cu prietenii sai mai mari.
Pana si aranjarea cartilor in mana e o problema pentru el. Cand primeste o mana
la carti, Vasilica trebuie sa aranjeze cartile pe grupe astfel incat cartile
din aceeasi grupa sa aiba aceeasi culoare, iar apoi trebuie sa ordoneze cartile
din fiecare grupa dupa valoare, astfel incat cartea cu cea mai mica valoare
sa fie plasata cat mai la stanga. Si, ce-i mai rau, el trebuie sa tina permanent
toate cartile in mana.
Vasilica trebuie sa aranjeze cartile cat mai rapid posibil, adica facand un
numar minim de mutari. O mutare consta in plasarea unei carti pe o alta pozitie.
Cerinta
Scrieti un program care sa determine numarul minim de mutari necesare pentru
ca Vasilica sa aranjeze cartile din mana.
Date de intrare
Fisierul de intrare carti2.in
contine pe prima linie doua numere naturale C (reprezentand numarul de culori
din jocul de carti) si N (reprezentand numarul de carti de aceeasi culoare),
separate printr-un spatiu.
Fiecare dintre urmatoarele C*N linii contine o pereche de numere naturale X
si Y, separate printr-un spatiu, reprezentand culoarea (X) si valoarea (Y) cartilor
pe care le-a tras Vasilica, in ordinea extragerii.
Date de iesire
Fisierul de iesire carti2.out
contine o singura linie pe care se afla numarul minim de mutari pe care trebuie
sa le faca Vasilica pentru a aranja toate cartile.
Restrictii
2 <= N <= 100
1 <= C <= 4
1 <= X <= C
1 <= Y <= N
Oricare doua carti extrase de Vasilica sunt distincte.
Exemple
carti2.in
carti2.out
2 2
2 1
1 2
1 1
2 2
2
carti2.in
carti2.out
4 1
2 1
3 1
1 1
4 1
0
carti2.in
carti2.out
3 2
3 2
2 2
1 1
3 1
2 1
1 2
2
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi