그래프 곱셈

그래프 이론에서 두 그래프의 곱은 여러 가지로 정의된다. 대표적으로 데카르트 곱, 텐서 곱, 강한 곱이 있다. 각 곱의 정의는 다음과 같다.

정점이 $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$개의 줄에 쿼리가 한 줄에 하나씩 주어진다. 쿼리 형식은 문제 설명을 참고한다.

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

각 쿼리의 답을 한 줄에 하나씩 출력한다.

• $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\}$