== include(page="template/taskheader" task_id="starcity") ==

Poveste şi cerinţă...

Se da un graf stea cu $N$ noduri. $N - 2$ noduri din cele $N$ au asociata o valoare distinca de la $1$ la $N - 2$, iar restul de $2$ sunt libere. O mutare consta din selectarea unei nod ocupat de o valoare si mutarea acestei valori intr-un nod vecin liber.
Un graf stea este un graf in care unul dintre noduri(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.
 
h2. Cerinta
 
Dandu-se o configuratie initiala si o configuratie finala, sa se spuna numarul minim de pasi si o secventa de mutari astfel incat sa se ajunga din configuratia initiala in cea finala.

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 configuratia initiala.
A treia linie contine configuratia la care trebuie sa se ajunga.

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

h2. Restricţii

* $... ≤ ... ≤ ...$

* $3 ≤ N ≤ 500.000$

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") ==