Problem:

カツサンド (Cutlet Sandwich)

ある世界には、 $X$ 種類の「サンド」、 $Y$ 種類の「カツ」、 $Z$ 種類の「カレー」という食べ物があります。

この世界には $N$ 種類の「カツサンド」という食べ物があり、 $i$ 種類目のカツサンドは $A_i$ 種類目のサンドと $B_i$ 種類目のカツが原料です。

また、 $M$ 種類の「カツカレー」という食べ物があり、 $i$ 種類目のカツカレーは $C_i$ 種類目のカツと $D_i$ 種類目のカレーが原料です。

Segtree 君は、あるカツサンドまたはカツカレーを持っているとき、原料のうち少なくとも $1$ つが共通しているようなカツサンドまたはカツカレーと交換することができます。

例えば、$a$ 種類目のサンドと $b$ 種類目のカツが原料であるカツサンドを持っているとき、 $a$ 種類目のサンドまたは $b$ 種類目のカツを原料に持つ任意のカツサンド、または、 $b$ 種類目のカツを原料に含む任意のカツカレーと交換できます。

今、 Segtree 君は $S$ 種類目のカツサンドを持っていますが、食べたいのは $T$ 種類目のカツカレーです。

$T$ 種類目のカツカレーを手に入れることができるか判定してください。もし可能ならば、最小何回の交換で目的のカツカレーを手にいられるかを求めてください。

入力

入力は以下の形式で標準入力から与えられる。

$X$ $Y$ $Z$ $N$ $M$ $S$ $T$
$A_1$ $B_1$
$A_2$ $B_2$
$\ldots$
$A_N$ $B_N$
$C_1$ $D_1$
$C_2$ $D_2$
$\ldots$
$C_M$ $D_M$

出力

 $T$ 種類目のカツカレーを手に入れるために必要な最小の交換回数を出力してください。手に入れることが不可能ならば、代わりに「 $-1$ 」を出力してください。

ただし、最後には改行を入れること。

制約

    
$1 \leq X,Y,Z,N,M \leq 10^5$

    
$1 \leq S \leq N$

    
$1 \leq T \leq M$

    
$1 \leq A_i \leq X$

    
$1 \leq B_i \leq Y$

    
$1 \leq C_i \leq Y$

    
$1 \leq D_i \leq Z$

    
入力は全て整数である。

入力例1

1 1 1 1 1 1 1
1 1
1 1    

出力例1

1

入力例2

2 3 4 3 5 1 5
1 1
1 2
2 2
2 1
3 1
3 2
3 3
3 4      

出力例2

4

入力例3

1 2 2 1 2 1 1
1 2
1 2
2 1

出力例3

-1



Sample input:
1 1 1 1 1 1 1
1 1
1 1


Sample output:
1

Submission status: Accepted

Solution code:
from itertools import *
from bisect import *
from math import *
from collections import *
from heapq import *
from random import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def MF(): return map(float, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LF(): return list(map(float, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    x,y,z,n,m,s,t=MI()
    s,t=s-1,t-1+n
    itoab=[]
    to1=defaultdict(list)
    to2=defaultdict(list)
    for i in range(n):
        a,b=MI1()
        itoab.append([a,b])
        to1[a].append(i)
        to2[b].append(i)
    for i in range(n,n+m):
        b,a=MI1()
        a+=x
        itoab.append([a,b])
        to1[a].append(i)
        to2[b].append(i)
    dist=[-1]*(n+m)
    hp=[]
    heappush(hp,[0,s])
    while hp:
        d,i=heappop(hp)
        if dist[i]!=-1:continue
        dist[i]=d
        a,b=itoab[i]
        for j in to1[a]:
            if j==t:
                print(d+1)
                exit()
            if j==i:continue
            if dist[j]!=-1:continue
            heappush(hp,[d+1,j])
        for j in to2[b]:
            if j==t:
                print(d+1)
                exit()
            if j==i:continue
            if dist[j]!=-1:continue
            heappush(hp,[d+1,j])
    print(-1)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

X,Y,Z,N,M,S,T=map(int,input().split())

CS=[[0,0,0]]+[list(map(int,input().split()))+[i+1]+[0] for i in range(N)]
CC=[[0,0,0]]+[list(map(int,input().split()))+[i+1]+[1] for i in range(M)]

CS_SLIST=[[] for i in range(X+1)]
CS_CLIST=[[] for i in range(Y+1)]
CC_CLIST=[[] for i in range(Y+1)]
CC_ULIST=[[] for i in range(Z+1)]

for x,y,z,_ in CS[1:]:
    CS_SLIST[x].append(z)
    CS_CLIST[y].append(z)

for x,y,z,_ in CC[1:]:
    CC_CLIST[x].append(z)
    CC_ULIST[y].append(z)

import heapq
MINCOST_CS=[1<<30]*(N+1)
MINCOST_CC=[1<<30]*(M+1)

MINCOST_CS[S]=0

Q=[[0]+CS[S]]
USES=[0]*(X+1)
USEC=[0]*(Y+1)
USEU=[0]*(Z+1)


while Q:
    #print(Q)
    cost,x,y,z,cs=heapq.heappop(Q)
    
    if cs==0:

        if USES[x]==0:
            USES[x]=1
            for to in CS_SLIST[x]:
                if MINCOST_CS[to]>cost+1:
                    MINCOST_CS[to]=cost+1
                    heapq.heappush(Q,[cost+1]+CS[to])

        if USEC[y]==0:
            USEC[y]=1

            for to in CS_CLIST[y]:
                if MINCOST_CS[to]>cost+1:
                    MINCOST_CS[to]=cost+1
                    heapq.heappush(Q,[cost+1]+CS[to])

            for to in CC_CLIST[y]:
                if MINCOST_CC[to]>cost+1:
                    MINCOST_CC[to]=cost+1
                    heapq.heappush(Q,[cost+1]+CC[to])

    else:

        if USEU[y]==0:
            USEU[y]=1
            for to in CC_ULIST[y]:
                if MINCOST_CC[to]>cost+1:
                    MINCOST_CC[to]=cost+1
                    heapq.heappush(Q,[cost+1]+CC[to])

        if USEC[x]==0:
            USEC[x]=1

            for to in CS_CLIST[x]:
                if MINCOST_CS[to]>cost+1:
                    MINCOST_CS[to]=cost+1
                    heapq.heappush(Q,[cost+1]+CS[to])

            for to in CC_CLIST[x]:
                if MINCOST_CC[to]>cost+1:
                    MINCOST_CC[to]=cost+1
                    heapq.heappush(Q,[cost+1]+CC[to])

#print(MINCOST_CS)
#print(MINCOST_CC)

if MINCOST_CC[T]==1<<30:
    print(-1)
else:
    print(MINCOST_CC[T])

Submission status: Accepted

Solution code:
from collections import deque
x,y,z,n,m,s,t=map(int,input().split())
g=[[]for _ in range(x+y+z)]
for i in range(n):
  a,b=map(int,input().split())
  g[a-1].append(b+x-1)
  g[b+x-1].append(a-1)
  if i==s-1:
    p,q=a-1,b+x-1
for j in range(m):
  a,b=map(int, input().split())
  g[a+x-1].append(b+x+y-1)
  g[b+x+y-1].append(a+x-1)
  if j==t-1:
    u,v=a+x-1,b+x+y-1
d=[-2]*(x+y+z)
d[p],d[q]=0,0
q=deque([p,q])
while q:
  p = q.popleft()
  for node in g[p]:
    if d[node]==-2:
      q.append(node)
      d[node]=d[p]+1
print(min(d[u],d[v])+1)