33851번 - DAG LCA

문제

무가중치 방향 비순환 그래프 $G$가 주어진다. 다음 쿼리를 수행하는 프로그램을 작성하시오.

• $u$ $v$: 두 정점 $u$와 $v$로 가는 경로가 모두 존재하는 모든 정점에 대해 $u$와 $v$로 가는 두 최단 경로의 길이 중 작지 않은 값의 최솟값을 출력한다. 두 정점 $u$와 $v$로 가는 경로가 존재하는 정점이 없다면 대신 -1을 출력한다.

입력

첫 번째 줄에 그래프 $G$의 정점의 개수 $n,ドル 간선의 개수 $m,ドル 질의의 개수 $q$가 공백으로 구분되어 주어진다. (5ドル \leq n \leq 2,000円; 0 \leq m \leq 4,000円; 1 \leq q \leq 1,000円$)

두 번째 줄부터 $m$개의 줄에 걸쳐 간선으로 연결된 두 정점의 번호 $u,ドル $v$가 한 줄에 하나씩 주어진다. 이는 $u$에서 $v$로 향하는 방향의 간선을 의미한다. (1ドル \leq u, v \leq n; u \neq v$)

$m+2$번째 줄부터 $q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다.

입력으로 주어지는 값은 모두 정수이며 무가중치 방향 비순환 그래프인 경우만 주어진다.

출력

쿼리가 주어질 때마다 쿼리의 답을 한 줄에 하나씩 출력한다.

제한

힌트