그래프 곱셈

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

정점이 $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\\}$