\(N\)개의 섬이 \(M\)개의 양방향 다리로 연결되어 있으며, 어떤 두 섬 사이도 다리들을 통해 오갈 수 있다. 두 섬을 직접 잇는 다리는 많아야 하나이다.

어떤 다리는 무너지면 두 섬 사이의 연결이 끊어질 수 있는 위험한 다리이다. \(Q\)개의 질의가 주어진다. 각 질의 \((u, v)\)에 대해, 하나만 무너져도 \(u\)에서 \(v\)로 갈 수 없게 되는 다리의 개수를 구하여라.

단절선을 모두 찾은 뒤, 이중 간선 연결 요소를 압축한 트리 위에서 경로 질의로 바꾸어 풀어야 한다.

\(2 \le N \le 100{,}000\)

\(N - 1 \le M \le 200{,}000\)

\(1 \le Q \le 100{,}000\)

그래프는 연결되어 있고, 자기 자신을 잇는 다리나 중복된 다리는 없다.

첫 줄에 \(N\)과 \(M\)이 주어진다.

다음 \(M\)개의 줄에 다리가 잇는 두 섬 \(a\), \(b\)가 주어진다.

다음 줄에 질의의 수 \(Q\)가 주어지고, 이어지는 \(Q\)개의 줄에 \(u\), \(v\)가 주어진다.

각 질의의 답을 입력 순서대로 한 줄에 하나씩 출력한다.

riseoj 작성

출처 Original