전장의 형제들

중세 시대에는 대부분의 도시가 인터넷에 접근할 수 없었기 때문에 도시 사이의 관계를 추적하기가 매우 어려웠다[citation needed]. 하지만 각 도시의 문장(紋章)을 살펴보면 두 도시가 서로 우호적인지 판단할 수 있었다. 모든 문장에는 두 개의 상징이 표시되었는데, 하나는 위쪽에, 다른 하나는 아래쪽에 있었다. 두 도시의 위쪽 상징이 같거나 아래쪽 상징이 같으면 두 도시는 우호적이다.

"내 친구의 친구는 나의 친구다"라는 말에 따라, 도시 $c\_0$과 $c\_f$는 $0\leq k < f$인 모든 $k$에 대해 $c\_k$와 $c\_{k+1}$이 우호적이 되도록 하는 도시 $c\_1, \ldots, c\_{f-1}$이 존재하면 간접적으로 우호적이다. $c\_0$과 $c\_f$가 서로 다르고 간접적으로 우호적이면, 이 정의를 따르는 가장 작은 $f$를 두 도시의 우호도라고 한다. 예시는 그림 B.1을 참고하라.

이 문장들의 일부는 Wikimedia Commons에 CC BY-SA 4.0 라이선스로 공개되어 있다.

그림 B.1: 입력 예시 1의 설명. 도시 1과 2는 직접 우호적이고, 도시 2와 3도 그렇다. 도시 1과 3은 도시 2를 거쳐 간접적으로 우호적이므로 우호도가 2이다. 도시 4는 다른 어떤 도시와도 (간접적으로) 우호적이지 않다.

문장 목록과 질의 목록이 주어진다. 각 질의마다 주어진 두 도시의 우호도를 구하라.

입력은 다음과 같이 주어진다.

첫 줄에 두 정수 $n$과 $s$가 주어진다 ($2\leq n\leq 90\,000$, $2\leq s\leq 300$). $n$은 도시의 수이고, $s$는 어떤 도시의 문장에든 나타날 수 있는 상징의 개수이다.

이어지는 $n$개 줄의 $i$번째 줄에는 두 정수 $t_i$와 $b_i$ ($1\leq t_i, b_i\leq s$)가 주어진다. $t_i$는 $i$번째 도시 문장의 위쪽 상징이고, $b_i$는 아래쪽 상징이다. $i\neq j$이면 $t_i\neq t_j$ 또는 $b_i\neq b_j$이다.

다음 줄에 정수 $q$ ($1\leq q\leq 10^5$)가 주어진다. 질의의 개수이다.

이어지는 $q$개 줄의 $i$번째 줄에는 두 정수 $c$와 $d$ ($1\leq c, d\leq n$, $c\neq d$)가 주어진다. 이 두 도시의 우호도를 구하라.

각 질의마다 두 도시의 우호도를 나타내는 정수를 출력한다. 두 도시가 (간접적으로도) 우호적이지 않으면 $-1$을 출력한다.