시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)1301008680.374%

문제

하늘이는 휴가 때마다 기차를 타고 집으로 간다. 기찻값을 지원받기 위해서는 어떤 기차역을 거치는지 알아야 하므로 하늘이는 미리 휴가 계획을 세우기로 결심했다.

기차역은 $N$개가 있고 이를 잇는 노선은 $M$개가 있다. 각 노선은 서로 다른 두 개의 기차역을 양방향으로 잇는다. 특이하게도 $i$번째 노선은 이동에 $2^i$분이 걸린다. 또한 모든 기차역에서 다른 모든 기차역으로 이동할 수 있다.

소중한 휴가 때 집으로 가는 데에 시간을 낭비할 수는 없기 때문에, 하늘이는 항상 최단 시간이 걸리는 경로를 이용한다. 그러한 경로가 여러 개라면, 거치는 기차역이 가장 적은 경로를 이용한다.

하늘이에게 남은 $Q$번의 휴가에 대해서 각 휴가마다 출발하는 기차역과 도착하는 기차역이 주어졌을 때, 몇 개의 기차역을 거쳐야 하는지 구해주자. 단, 출발하고 도착하는 기차역은 세지 않는다.

입력

첫째 줄에 $N$과 $M$이 공백을 사이에 두고 주어진다. ($2\le N\le 200\, 000;$ $N-1\leq M\leq 200\, 000$)

둘째 줄부터 $M$개의 줄에 걸쳐 각 노선이 잇는 기차역의 번호를 나타내는 정수 $u_i$, $v_i$가 공백을 사이에 두고 주어진다. 해당 노선은 이동에 $2^i$분이 걸린다. 같은 기차역을 잇는 노선이 여러 개 존재할 수 있음에 유의하시오. $(1\le u_i,v_i\le N;$ $u_i\neq v_i;$ $1\le i\le M)$

$M+2$번째 줄에 $Q$가 주어진다. ($1\le Q\le 200\, 000$)

$M+3$번째 줄부터 $Q$개의 줄에 걸쳐 출발하는 기차역과 도착하는 기차역의 번호를 나타내는 정수 $s_i,e_i$가 공백을 사이에 두고 주어진다. $(1\le s_i,e_i\le N;$ $s_i\neq e_i;$ $1\le i\le Q)$

출력

$Q$개의 줄에 걸쳐 각 쿼리에 대한 정답을 출력한다.

예제 입력 1

3 3
1 2
1 3
2 3
3
1 2
1 3
2 3

예제 출력 1

0
0
1

예제 입력 2

4 5
3 2
3 4
2 4
1 3
1 2
6
1 2
1 3
1 4
2 3
2 4
3 4

예제 출력 2

1
0
1
0
1
0

출처

Contest > 보라매컵 > 제4회 보라매컵 F번