arb1

Cerință

Vârcolacul Marian a hotărât că pe timp de noapte, beciul în care își ține murăturile trebuie închis. Pentru că are multe murături, beciul este format din $N$ camere conectate prin $N - 1$ muchii (deci beciul are formă de arbore și are rădăcina în $1$). Inițial, toate camerele sunt deschise.

Într-o operație, Marian poate alege două camere încă deschise $x$ și $y$ și să închidă toate camerele de pe drumul direct de la $x$ la $y$, mai puțin LCA-ul lor.

Pentru ca o operație să fie validă, trebuie respectate următoarele două reguli:

1. În fiecare operație, LCA-ul trebuie să fie diferit de $x$ și de $y$.
2. După fiecare operație, camerele care rămân deschise trebuie să fie în continuare conectate între ele. Mai exact, trebuie să se poată ajunge de la orice cameră rămasă deschisă la oricare alta, deplasându-ne exclusiv prin camere care nu au fost încă închise.

• LCA (Cel mai mic strămoș comun) este definit ca fiind nodul cel mai apropiat de rădăcină de pe drumul direct de la $x$ la $y$.

Care este numărul minim de operații astfel încât la final singura cameră deschisă să rămână rădăcina? (Marian va dori să lase o cameră deschisă pentru cazul în care i se va face foame peste noapte).

Date de intrare

Pe prima linie se află numărul natural $N$. Pe următoarea linie se află $N - 1$ numere naturale, al $i$-lea număr reprezentând părintele camerei $i + 1$.

Date de ieșire

Dacă acest lucru nu este posibil, se va afișa -1. Altfel, pe prima linie se va afișa $K$, reprezentând numărul minim de operații. Pe următoarele $K$ linii se vor afișa două valori $x$ și $y$, reprezentând operațiile alese.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$;
• $1 \leq p[i] \leq N$ și $p[i] \neq i + 1$;
• Pentru $1 \leq N \leq 1000$, se acordă 30 de puncte;
• Pentru determinarea corectă a numărului minim de operații, se acordă 20% din punctajul testului;
• Dacă există mai multe soluții care obțin numărul minim de operații, se va accepta oricare dintre acestea.

Exemplul 1

stdin

3
1 1

stdout

1
2 3

Explicație

Arborele este format din rădăcina $1$, care are doi fii: $2$ și $3$.
Alegem $x = 2$ și $y = 3$. LCA-ul lor este $1$ (care este diferit de $2$ și de $3$).
Drumul direct între $2$ și $3$ este $2 - 1 - 3$. Se închid camerele $2$ și $3$, excepție făcând LCA-ul ($1$).
Singura cameră rămasă deschisă este $1$, iar condiția de conectivitate este respectată. Numărul minim de operații este $1$.

Exemplul 2

stdin

2
1

stdout

-1

Explicație

Arborele este format din rădăcina $1$ și fiul ei $2$. Singura cameră care trebuie închisă este $2$. Nu putem alege două camere deschise $x$ și $y$ astfel încât LCA-ul să fie diferit de ambele (dacă am alege $1$ și $2$, LCA-ul lor ar fi $1$, ceea ce ar încălca prima regulă a operației valide). Astfel, problema nu are soluție.