== include(page="template/taskheader" task_id="hansha") ==
Poveste şi cerinţă...
Dupa numeroasele probleme cu palindromuri pe care le-a compus Dani, colegii sai de echipa i-au spus sa-si mai improspateze ideile, fiindca toata lumea s-a plictisit de ele. Dani a fost de-acord, dar n-a renuntat la pasiunea sa mai generala pentru simetrie. De aceasta data, el s-a inspirat din istoria imperiului antic Hansha, a carui dezvoltare i s-a parut foarte interesanta. Initial, imperiul Hansha era constituit dintr-un singur oras, iar acesta avea un numar pe post de nume: numarul $1$. Apoi, in fiecare secol, timp de $K$ secole, imperiul s-a dezvoltat astfel: Numarul sau de orase s-a dublat, iar daca orasele sale erau numerotate pana acum cu valori de la $1$ la $N$, noile orase vor lua drept nume valorile $N + 1, N + 2... 2 * N$. Mai mult, aceste $N$ noi orase vor avea exact aceeasi structura de drumuri ca orasele initiale. Mai exact, va exista drum intre orasul $N + i$ si orasul $N + j$, unde $1 ≤ i, j ≤ N$ daca si numai daca exista deja un drum intre orasele $i$ si $j$. Astfel, se poate spune ca in acest moment al fazei de dezoltare, imperiul s-a "oglindit", formand doua copii identice. Pentru a conecta aceste copii, se va mai construi un singur nou drum care va conecta un oras duplicat de corespondentul sau. Mai exact, pentru un unic $1 ≤ x ≤ N$, se va adauga un drum intre nodurile $x$ si $N + x$. Acest $x$ poate varia de la o faza de dezvoltare la alta.
Dani are in fata mai multe scenarii posibile ale dezvoltarii imperiului Hansha. Un scenariu este definit printr-un numar $K$, care reprezinta numarul de faze de dezvoltare si descrierea celor $K$ valori $x$, numerele oraselor care vor fi conectate cu duplicatul lor la fiecare dintre cele $K$ faze ale dezvoltarii. Pentru fiecare scenariu, Dani va intreaba care este numarul minim de drumuri pe care trebuie sa-l parcurga pentru a ajunge din orasul $A$ in orasul $B$ dupa ce s-au finalizat toate etapele de dezvoltare in scenariul respectiv.
h2. Date de intrare
Fişierul de intrare $hansha.in$ ...
Fişierul de intrare $hansha.in$ va contine pe prima sa linie, valoarea $T$, reprezentand numarul de scenarii ce vor fi analizate. Urmeaza cele $T$ scenarii, formatul unui scenariu fiind urmatorul: Pe prima linie se afla valoarea $K$, reprezentand numarul de faze de dezvoltare din scenariul respectiv. Urmeaza o linie cu $K$ valori, reprezentand numarul orasului ce va fi conectat cu duplicatul sau in fiecare faza de dezvoltare. A treia linie va contine doua valori $A$ si $B$, reprezentand numerele oraselor de a caror distanta este interesat Dani.
h2. Date de ieşire
În fişierul de ieşire $hansha.out$ ...
În fişierul de ieşire $hansha.out$ se vor afla $T$ valori, a $i$-a dintre acestea reprezentand raspunsul pentru intrebarea lui Dani din scenariul cu numarul $i$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 1.000$
* $1 ≤ K ≤ 30$
* Pentru $40$ de puncte $1 ≤ K ≤ 10$
h2. Exemplu
table(example). |_. hansha.in |_. hansha.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|3
4
1 2 3 4
1 16
4
1 2 4 7
2 13
5
1 2 4 6 10
3 30
|6
7
11
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="hansha") ==
