3dist

Cerință

Se dă un arbore cu $N$ noduri. Notăm cu $dist(x,y)$ lungimea celui mai scurt drum dintre nodurile $x$ și $y$.

Se dau $Q$ query-uri de tipul $(D_1, D_2, D_3)$, pentru fiecare query trebuie să găsești $4$ noduri $a,b,c,d$ care să respecte condițiile ca $dist(a,b)=D_1$, $dist(a,c)=D_2$, $dist(a,d)=D_3$ și ca drumurile $a-b$, $a-c$, $a-d$ să nu se intersecteze (să nu aibă nicio muchie în comun).

Date de intrare

Pe prima linie se află 2 numere întregi, $N \leq 10^5$ și $Q \leq 2 \times 10^5$.
Pe fiecare din următoarele $N-1$ linii se află câte $2$ numere întregi $U_i$ și $V_i$, reprezentând o muchie între $U_i$ și $V_i$.
Pe fiecare din următoarele $Q$ linii se vor afla $3$ numere naturale nenule, reprezentând un query.

Date de ieșire

Se vor afla $Q$ linii, pe a $i$-a linie se va afișa răspunsul la al $i$-lea query. Dacă există $4$ noduri care respectă condițiile query-ului se va afișa DA urmat de $4$ numere întregi reprezentând cele $4$ noduri. Dacă nu, se va afișa doar NU.

Restricții și precizări

Exemplu

stdin

7 3
7 1
7 4
4 3
6 1
5 6
6 2
3 1 1
1 1 1
2 1 1

stdout

DA 6 4 5 2
DA 6 1 5 2
DA 6 7 5 2