32988번 - 그래프 곱셈

문제

그래프 이론에서 두 그래프의 적(곱)연산은 여러 가지가 정의되어 있는데, 대표적으로는 데카르트적, 텐서적, 강적이 있다. 이들의 정의는 다음과 같다.

정점이 $N$개인 그래프 $A$의 정점을 $A_i$ $(1 \leq i \leq N),ドル 정점이 $M$개인 그래프 $B$의 정점을 $B_i$ $(1 \leq i \leq M)$라 하자. 이때, 두 그래프를 곱한 새로운 그래프 $G$는 $N\times M$개의 정점을 가진다. 각 정점에 다음과 같은 번호를 붙이자: $G_{11}, G_{12}, \cdots, G_{1M}, G_{21}, \cdots, G_{NM}$.

이때, 연산별로 간선은 다음과 같이 정의된다.

• 데카르트적: 1ドル\leq i,j\leq N$ ($i \neq j$)에 대해 $A_i$와 $A_j$가 인접하다면 1ドル \leq k \leq M$에 대해 $G_{ik}$와 $G_{jk}$가 인접하고, 1ドル\leq i,j\leq M$ ($i \neq j$)에 대해 $B_i$와 $B_j$가 인접하다면 1ドル \leq k \leq N$에 대해 $G_{ki}$와 $G_{kj}$가 인접하다.
• 텐서적: 1ドル\leq i,j\leq N,ドル 1ドル\leq k,l\leq M$ ($i\neq j,ドル $k\neq l$)에 대해 $A_i$와 $A_j$가 인접하고 $B_k$와 $B_l$가 인접하다면 $G_{ik}$와 $G_{jl}$이 인접하다.
• 강적: 1ドル\leq i,j\leq N,ドル 1ドル\leq k,l\leq M$에 대해 $G_{ik}$와 $G_{jl}$이 데카르트적에서 인접하거나 텐서적에서 인접하다면 인접하다.

예를 들어, 아래 그림 1에서 왼쪽 두 그래프를 데카르트적 연산하면 오른쪽 그래프의 9개 정점과 파란색 실선으로 된 간선, 텐서적 연산하면 9개 정점과 빨간색 점선으로 된 간선을 얻는다.

[그림 1] 데카르트적, 텐서적, 강적을 그림으로 나타낸 예시.

이때, 두 그래프 $A$와 $B$가 주어지면 이 그래프에 대해 다음과 같은 쿼리 $Q$개에 대한 답을 출력하는 프로그램을 구현하시오.

• 1 p q: 그래프 $A$와 $B$의 데카르트적 $G$에 대해 두 정점 $G_{pq}$와 $G_{11}$ 사이의 최단경로의 길이를 출력하여라. 경로가 없다면 -1을 출력하여라.
• 2 p q: 그래프 $A$와 $B$의 텐서적 $G$에 대해 두 정점 $G_{pq}$와 $G_{11}$ 사이의 최단경로의 길이를 출력하여라. 경로가 없다면 -1을 출력하여라.
• 3 p q: 그래프 $A$와 $B$의 강적 $G$에 대해 두 정점 $G_{pq}$와 $G_{11}$ 사이의 최단경로의 길이를 출력하여라. 경로가 없다면 -1을 출력하여라.

입력

첫 번째 줄에 그래프 $A$의 정점의 개수 $N$과 간선의 개수 $X$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $X$개의 줄 중 $i$번째 줄에 그래프 $A$의 $i$번째 간선이 잇는 두 정점의 번호 $u_i$와 $v_i$가 공백으로 구분되어 주어진다.

그다음 줄에 그래프 $B$의 정점의 개수 $M$과 간선의 개수 $Y$가 공백으로 구분되어 주어진다.

그다음 줄부터 $Y$개의 줄 중 $i$번째 줄에 그래프 $B$의 $i$번째 간선이 잇는 두 정점의 번호 $u'_i$와 $v'_i$가 공백으로 구분되어 주어진다.

그다음 줄에 쿼리의 개수 $Q$가 주어진다.

그다음 줄부터 $Q$개의 줄에 쿼리가 한 줄에 하나씩 주어진다. 쿼리의 형식은 지문을 참고하여라.

주어지는 모든 입력은 정수이다.

출력

각 $Q$개의 쿼리에 대한 답을 한 줄에 하나씩 출력하여라.

제한

• 2ドル \leq N, M \leq 200,000円$
• 1ドル \leq X \leq \min\left(\cfrac{N\left(N-1\right)}{2}, 500,000円\right)$
• 1ドル \leq Y \leq \min\left(\cfrac{M\left(M-1\right)}{2}, 500,000円\right)$
• 1ドル \leq Q \leq 500,000円$
• 각 쿼리에 대해, 1ドル \leq p \leq N,ドル 1ドル \leq q \leq M$
• 1ドル \leq u_i, v_i \leq N$ (1ドル \leq i \leq X$)
• 1ドル \leq u'_i, v'_i \leq M$ (1ドル \leq i \leq Y$)
• $u_i \neq v_i$ (1ドル \leq i \leq X$)
• $u'_i \neq v'_i$ (1ドル \leq i \leq Y$)
• 1ドル \leq i, j \leq X$에 대해, $i \neq j$이면 $\{u_i,v_i\} \neq \{u_j,v_j\}$
• 1ドル \leq i, j \leq Y$에 대해, $i \neq j$이면 $\{u'_i,v'_i\} \neq \{u'_j,v'_j\}$

힌트