Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

WIESCZ - Wierzchołki na ściezce

Mamy dany spójny, acykliczny graf. Dla pewnych wierzchołków v chcielibyśmy poznać numer k-tego wierzchołka na ich ścieżce do wierzchołka numer 1.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n oraz m (1  n, m  106), oznaczające kolejno liczbę wierzchołków w grafie oraz liczbę zapytań.

Kolejne n – 1 wierszy zawiera opis krawędzi w grafie. W każdym z nich znajdują się dwie liczby całkowite a i b (1  a, b n) oznaczające, że krawędź łącząca wierzchołek a i b.

Kolejne m wierszy zawiera opisy kolejnych zapytań, po jednym w wierszu. Opis każdego zapytania składa się z dwóch liczb całkowitych v oraz k (1  v, k  n), oznaczających, że szukamy numeru k-tego wierzchołka na ścieżce od wierzchołka v do wierzchołka numer 1. Wartość k nie przekracza długości ścieżki pomiędzy wierzchołkiem 1, a v.

Wyjście

W m wierszach wyjścia powinny znaleźć się odpowiedzi na kolejne zapytania, po jednej w wierszu. 

Przykład

Dla danych wejściowych:

8 4

1 2

1 5

5 7

5 8

4 8

6 8

3 5

6 2

3 1

5 2

6 3

poprawnym wynikiem jest:

8

3

1

5


Dodane przez:Karol Waszczuk
Data dodania:2014-08-13
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.