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

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.

Un graf stea este un graf in care unul dintre noduri(numit centrul grafului, notat cu 1) 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.

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. Sa se determine numarul minim de mutari pentru a transforma graful initial intr-un alt graf dat.
 

h2. Date de intrare

h2. Restricţii

* $3 ≤ N ≤ 500.000$

* $3 ≤ N ≤ 100.000$
* Daca solutia data este valida, dar numarul de mutari nu este minim, se va acorda $40%$ din punctaj.

h2. Exemplu