33283번 - 휴가 계획

문제

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

기차역은 $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$개의 줄에 걸쳐 각 쿼리에 대한 정답을 출력한다.

제한

힌트