graph
Zadato je stablo (neorijentisani ciklični graf) sa N čvorova. Zatim još M upita od po 2 broja, koji predstavljanju neka 2 čvora. Vaš zadatak je da pronadjete najbližeg zajedničkog pretka za ta dva čvora. Čvorovi su zadati brojevima od 1 do N. Čvor 1 je glavni koren stabla.
InputU prvom redu standardnog ulaza nalaze se dva cela broja N ( 1 <= N <= 10^6 ), i M ( 1 <= M <= 10^6 ). U sledećih N-1 redova nalaze se po dva broja , A i B, i oni označavaju granu koja povezuje čvorove A i B. U sledećih M redova su upiti, opet u vidu 2 cela broja , A B.
OutputZa svaki upit, potrebno je u posebnom redu ispisati najbližeg zajedničkog pretka.
Ulaz:
7 3
1 2
1 3
3 4
3 5
5 6
6 7
7 4
6 2
6 7Izlaz::
3
1
6
Image: graph2
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.