AlgoLiga 2018

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*10⁵, 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