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.|

AL_18_04 - Na rowerze przez Bitlandię

Bitłomiej jest zapalonym rowerzystą. Codziennie przemierza dziesiątki bitometrów przemierzając krainę Bitocji. Niestety wraz z rodzicami, Bitłomiej przeprowadził się do Bitlandii. Niestety, gdyż charakterystyczną cechą tamtejszego klimatu jest duże nasycenie silnych wiatrów. Nasz bohater zalicza się do tych rowerzystów, którzy nienawidzą wiatr nawet bardziej od deszczu. Bitłomiej postanowił zrobić sobie mapę, na której pozaznaczał miejsca, o które mógłby zahaczyć. Naniósł również na mapie połączenia między tymi punktami, zaznaczając w którą stronę wieje wiatr na każdej drodze. Na szczęście, na danym odcinku wiatr wieje zawsze w tę samą stronę, a kierunek wiatru się nie zmienia na odcinku. Mając taką mapę pozostało mu już tylko napisać program, który obliczy jaka jest najmniejsza ilość odcinków, które Bitłomiej musi pokonać pod wiatr, jadąć z punktu a do punktu b. Jako że jest to tylko historyjka będąca pretekstem do zaimplementowania konkretnego algorytmu, Ty musisz napisać ten program.

Wejście

W pierwszej linii znajdują się liczby n i m (1 ≤ n,m ≤ 2*105, n > 1) - ilość wierzchołków oraz krawędzi w grafie. Kolejne m linii zawiera dwie liczby x i y (1 ≤ x, y ≤ n), które oznaczają, że wiatr wieje z punktu x do punktu y. Następnie pojawia się liczba q (q ≤ 1000) będąca liczbą zapytań. Każde z q zapytań to jedna linia z liczbami a i b (1 ≤ a, b ≤ n).

Wyjście

Dla każdego zapytania liczba odcinków, które Bitłomiej musi pokonać pod wiatr, by dostać się z punktu a do punktu b. Jeśli nie ma połączenia między owymi punktami, należy wypisać NIE.

Przykład

Wejście:
7 7
2 1
5 6
3 4
1 6
2 3
6 4
3 6
4
2 4
3 1
5 2
6 7 Wyjście: 0
1
2
NIE

Dodane przez:Piotr Kąkol
Data dodania:2014-08-29
Limit czasu wykonania programu:0.5s-2.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.