휴가 계획

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

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

휴가 시간을 낭비하지 않으려고 하늘이는 항상 최단 시간이 걸리는 경로를 이용한다. 그러한 경로가 여러 개라면, 거치는 기차역이 가장 적은 경로를 이용한다.

남은 $Q$번의 휴가마다 출발하는 기차역과 도착하는 기차역이 주어진다. 각 휴가에서 하늘이가 거쳐야 하는 기차역의 수를 구하라. 단, 출발하고 도착하는 기차역은 세지 않는다.

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

둘째 줄부터 $M$개의 줄에 걸쳐 각 노선이 잇는 기차역의 번호 $u_i$, $v_i$가 공백을 사이에 두고 주어진다. 해당 노선은 이동에 $2^i$분이 걸린다. 같은 두 기차역을 잇는 노선이 여러 개 있을 수 있다. ($1\le u_i,v_i\le N$, $u_i\ne 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\ne e_i$, $1\le i\le Q$)

$Q$개의 줄에 걸쳐 각 휴가에 대한 답을 출력한다.