== 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. Date de intrare

Fişierul de intrare $fantasy.in$ va conţine pe prima linie $4$ numere naturale $N$, $D$, $C$, $V$ reprezentănd numărul de camere din labirint, respectiv indicii camerelor în care se află $Dragonul(D)$, $Cavalerul( C)$ şi respectiv $Vrăjitorul(V)$.
Următoarele $N - 1$ vor conţine câte două valori fiecare $x$ si $y$ cu semnificaţia ca exista o legătura între camerele cu indicii $x$ si $y$.

Fişierul de intrare $fantasy.in$ va conţine pe prima linie valorea $T$ reprezentand numarul de teste din fisier. Un test are urmatoarea structura:
 
Pe prima sa linie exista $4$ numere naturale $N$, $D$, $C$, $V$ reprezentănd numărul de camere din labirint, respectiv indicii camerelor în care se află $Dragonul(D)$, $Cavalerul( C)$ şi respectiv $Vrăjitorul(V)$.
Următoarele $N - 1$ linii vor conţine câte două valori fiecare $x$ si $y$ cu semnificaţia ca exista o legătura între camerele cu indicii $x$ si $y$.

Aceste $N - 1$ legături vor descrie un arbore.
h2. Date de ieşire

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
table(example). |_. fantasy.in |_. fantasy.out |

| 4 2 4 3

| 3
4 2 4 3

1 3
2 3
3 4

| DA
|
| 4 3 4 1

4 3 4 1

1 2
2 3
3 4

| NU

3 1 3 2
1 2
2 3
| DA
NU
NU

|
h3. Explicaţie

în al doilea exemplu, vrăjitorul orice ar face va prins de câtre dragon orice ar face,

În al treilea exemplu, vrăjitorul este prins între cei doi si poate alege fie sa se deplaseze spre cavaler, omorăndu-l si rămanand singur cu dragonul, sau să ramană pe loc şi toţi 3 vor fi în acelaşi nod şi vor pieri.

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