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

Acum mulţi mulţi ani in Regatul cel Mare din Cluj trăiau un vrăjitor vestit, un dragon si un cavaler cu o sabie fermecată într-un echilbru care era gata gata să dispară. Cei trei nu se înţelegeau deloc, însa niciunul nu era suficinet de puternic să scape de ceilalţi doi. Astfel vrăjitorul putea la orice moment să iţi folosească magia să omoare cavalerul. Cavalerul la rândul lui putea oricând cu o lovitură a sabiei sale fermecate să omoare dragonul, iar dragonul fiind complet imun la magia vrăjitorului putea oricând să îl manance.
Niciunul din cei trei nu se risca să-l inlăture pe cel pe care îl putea învinge deoarece ar fi fost neputioncos împotriva celui rămas. De exemplu dacă vrajitorul ar fi încercat să scape de cavaler, dragonul ar fi putut să scăpa de el.

Acum mulţi mulţi ani in Regatul cel Mare din Cluj trăiau un vrăjitor vestit, un dragon si un cavaler cu o sabie fermecată într-un echilbru care era gata gata să dispară. Cei trei nu se înţelegeau deloc, însa niciunul nu era suficient de puternic incat să scape de ceilalţi doi. Astfel vrăjitorul putea la orice moment să isi folosească magia să omoare cavalerul. Cavalerul la rândul lui putea oricând cu o lovitură a sabiei sale fermecate să omoare dragonul, iar dragonul fiind complet imun la magia vrăjitorului putea oricând să îl manance.
Niciunul din cei trei nu se risca să-l inlăture pe cel pe care îl putea învinge deoarece ar fi fost neputincios împotriva celui rămas. De exemplu dacă vrajitorul ar fi încercat să scape de cavaler, dragonul ar fi putut scăpa de el.

Într-o zi însa vrajitorul, din noroc (sau poate din ghinion) a reuşit sa-i teleporteze pe el, dragon si cavaler într-un labirit sub forma unui arbore (graf neorientat conex aciclic), unde camerele labirintului reprezintă nodurile arborelui, iar o legatură între $2$ camere reprezintă o muchie din arbore.

Într-o zi însa vrajitorul, din noroc (sau poate din ghinion) a reuşit sa se teleporteze pe el insusi, pe dragon si pe cavaler într-un labirit sub forma unui arbore (graf neorientat conex aciclic), unde camerele labirintului reprezintă nodurile arborelui, iar o legatură între doua camere reprezintă o muchie din arbore.

Din acel moment în fiecare secundă fiecare din cele $3$ personaje fie s-au deplasat într-o celula adiacentă cu celula în care s-au aflat în secunda anterioara, fie au rămas pe loc. Daca la un moment dat $2$ din cele $3$ personaje se întalnesc, atunci cel mai puternic dintre cei doi îl omoară instantaneu pe celalalt, indiferent daca se întalnesc într-o cameră sau pe o legătură.

Din acel moment, în fiecare secundă, fiecare dintre cele trei personaje fie s-a deplasat într-o celula adiacentă cu celula în care s-a aflat în secunda anterioara, fie a rămas pe loc. Daca la un moment dat doua din cele trei personaje se întalnesc, atunci cel mai puternic dintre cei doi îl omoară instantaneu pe celalalt, indiferent daca se întalnesc într-o cameră sau pe o legătură.

Astfel:

h2. Restricţii

* $1 ≤ N ≤ 100.000$

* $1 ≤ T ≤ 100$
* $1 ≤ N ≤ 1.000$

* $1 ≤ D, C, V, x, y ≤ N$
* $D ≠ C, D ≠ V, C ≠ V$
* $Dragonul, Cavalerul şi Vrăjitorul se mută deodata în labirint$
* $Daca cei 3 se întălnesc în acelaşi nod în aceeaşi secundă, atunci toţi 3 vor muri$

* Pentru teste in valoare de $30$ de puncte $1 ≤ N ≤ 200$ si $1 ≤ T ≤ 30$.

h2. Exemplu