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

Regele Gefghev se confruntă cu o nouă problemă de interes naţional. Regatul condus de el conţine $N$ oraşe, numerotate de la $1$ la $N$, legate între ele prin $N–1$ poteci bidirecţionale. Fiecare potecă are o anumită lungime exprimată în metri. Între oricare două oraşe există cel mult o singură potecă şi se poate ajunge din orice oraş în oricare alt oraş, mergând numai pe potecile existente. Regelui îi place să călătorească, de aceea el îşi ia
concediu $M$ zile şi plănuieşte să organizeze $M$ călătorii. La începutul fiecărei zile Gefghev alege un oraş de pornire $x$ şi vrea să parcurgă începând cu acel oraş un drum de lungime maximă. Drumul parcurs de rege este
de fapt o succesiune de oraşe distincte ( $a{~1~}$ , $a{~2~}$ , $a{~3~}$ ... $a{~k-1~}$ , $a{~k~}$ ) astfel încât există o potecă între oricare două oraşe $a{~i~}$ şi $a{~i+1~}$ $(i < k)$ iar $a{~1~}$ $= x$. Lungimea drumului este dată de suma lungimilor potecilor care-l compun. Fiindcă nu vrea să se plictisească, regele Gefghev vrea să parcurgă în fiecare zi un drum diferit. Două
drumuri $d{~1~}$ = ( $a{~1~}$ , $a{~2~}$ , $a{~3~}$ ... $a{~k-1~}$ , $a{~k~}$ ) şi $d{~2~}$ = ( $b{~1~}$ , $b{~2~}$ , $b{~3~}$ ... $b{~p-1~}$ , $b{~p~}$ ) sunt diferite dacă:

Regele Gefghev se confruntă cu o nouă problemă de interes naţional. Regatul condus de el conţine $N$ oraşe, numerotate de la $1$ la $N$, legate între ele prin $N–1$ poteci bidirecţionale. Fiecare potecă are o anumită lungime exprimată în metri. Între oricare două oraşe există cel mult o singură potecă şi se poate ajunge din orice oraş în oricare alt oraş, mergând numai pe potecile existente. Regelui îi place să călătorească, de aceea el îşi ia concediu $M$ zile şi plănuieşte să organizeze $M$ călătorii. La începutul fiecărei zile Gefghev alege un oraş de pornire $x$ şi vrea să parcurgă începând cu acel oraş un drum de lungime maximă. Drumul parcurs de rege este de fapt o succesiune de oraşe distincte ( $a{~1~}$ , $a{~2~}$ , $a{~3~}$ ... $a{~k-1~}$ , $a{~k~}$ ) astfel încât există o potecă între oricare două oraşe $a{~i~}$ şi $a{~i+1~}$ $(i < k)$ iar $a{~1~}$ $= x$. Lungimea drumului este dată de suma lungimilor potecilor care-l compun. Fiindcă nu vrea să se plictisească, regele Gefghev vrea să parcurgă în fiecare zi un drum diferit. Două drumuri $d{~1~}$ = ( $a{~1~}$ , $a{~2~}$ , $a{~3~}$ ... $a{~k-1~}$ , $a{~k~}$ ) şi $d{~2~}$ = ( $b{~1~}$ , $b{~2~}$ , $b{~3~}$ ... $b{~p-1~}$ , $b{~p~}$ ) sunt diferite dacă:

* $k ≠ p$ sau
* $k = p$ şi există măcar o poziţie $q$ astfel încât $a{~q~} ≠ b{~q~}$

Scrieţi un program care determină pentru regele Gefghev lungimea drumului parcurs în fiecare din cele $M$ călătorii.
h2. Date de intrare