시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1536 MB 665 168 141 33.732%

문제

나무 $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$는 중복 간선과 자기 자신으로 향하는 간선이 없는 연결 그래프다.

예제 입력 1

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

예제 출력 1

1
1

출처

Contest > Good Bye, BOJ > Good Bye, BOJ 2020! C번