== include(page="template/taskheader" task_id="starcity") ==
Poveste şi cerinţă...
Un graf stea este un graf in care unul dintre noduri (nodul $1$, numit centrul grafului) este conectat printr-o muchie cu fiecare dintre celelalte noduri, iar fiecare nod din cele $N - 1$ ramase este conectat doar cu centrul grafului. Daca vreti sa vi-l imaginati arata ca o roata de bicicleta in care muchiile grafului sunt spitele bicicletei.
h2. Cerinta
Se da un graf stea cu $N$ noduri. $N - 2$ noduri din cele $N$ au asociata o valoare unică de la $1$ la $N - 2$, iar restul de $2$ sunt libere. O mutare constă în selectarea unui nod ocupat de o valoare si mutarea acestei valori intr-un nod vecin liber. Sa se determine numarul minim de mutari pentru a transforma graful initial intr-un alt graf dat.
h2. Date de intrare
Fişierul de intrare $starcity.in$ ...
Fişierul de intrare $starcity.in$ contine 3 linii.
Pe prima linie va fi dat numarul natural $N$.
A doua linie contine numerele asociate fiecarui nod din graf, incepand cu nodul $1$ (centrul) si pana la $n$. Daca un nod este initial gol, se considera ca numarul asociat acestuia este $0$.
A treia linie contine tot $n$ numere: pentru fiecare nod, numarul ce trebuie sa fie in el in urma mutarilor, sau $0$ daca nodul trebuie sa fie gol.
h2. Date de ieşire
În fişierul de ieşire $starcity.out$ ...
În fişierul de ieşire $starcity.out$ se va afisa pe prima line numarul minim de mutari $K$. Pe pe fiecare din urmatoarele $K$ linii se vor afisa doua numere naturale $x$ si $y$ care reprezinta mutarea valorii din nodul $x$ in nodul $y$. Nodurile $x$ si $y$ trebuie sa fie vecine, nodul $x$ trebuie sa contina un numar iar nodul $y$ sa fie gol ca mutarea sa fie valida.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $3 ≤ N ≤ 100.000$
* Daca solutia data este valida, dar numarul de mutari nu este minim, se va acorda $40%$ din punctaj.
h2. Exemplu
table(example). |_. starcity.in |_. starcity.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
0 0 1 2
0 0 2 1
| 6
3 1
1 2
4 1
1 3
2 1
1 4
|
h3. Explicaţie
...
Graful stea va trece prin urmatoarele stari:
$0 0 1 2$
$1 0 0 2$
$0 1 0 2$
$2 1 0 0$
$0 1 2 0$
$1 0 2 0$
$0 0 2 1$
== include(page="template/taskfooter" task_id="starcity") ==
