20530번 - 양분

나무 $T$는 양분을 먹고 자란다.

원래 나무는 정점 $N$개와 간선 $N-1$개로 구성되어야 하지만, 양분을 너무 많이 먹어버린 나머지 나무 $T$는 $N$개의 간선을 갖게 되었다. 더 이상 트리가 아니기 때문에 $T$는 꿈의 무대인 트리와 쿼리에 등장하지 못한다. 슬퍼하고 있는 $T$를 위해 정휘는 새로운 문제를 만들어 주었다.

$N$개의 정점과 $N$개의 간선으로 이루어진 연결 그래프 $T$가 주어진다. 정점은 1번부터 $N$번까지 번호가 매겨져 있고, 간선도 1번부터 $N$번까지 번호가 매겨져 있다. 아래 쿼리를 수행하는 프로그램을 작성하시오.

• $u \ v$ : $u$번 정점에서 $v$번 정점으로 가는 단순 경로의 수를 출력한다.

첫째 줄에 두 자연수 $N$, $Q$가 주어진다. 주어지는 그래프의 정점과 간선의 개수가 $N$개이며 쿼리가 $Q$개 주어진다는 것을 의미한다.

둘째 줄부터 $N$개의 줄에는 $i$번 간선이 연결하는 두 정점 번호 $a$, $b$가 주어진다.

다음 $Q$개 줄에는 쿼리가 한 줄에 하나씩 주어진다.

• $1 \leq N, Q \leq 200\,000$
• $1 \leq a, b, u, v \leq N$
• $a \ne b$
• $u \ne v$
• 입력으로 주어진 그래프 $T$는 중복 간선과 자기 자신으로 향하는 간선이 없는 연결 그래프다.