ある世界には、 $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 1 1 1 1 1 1 1 1 1 1
1
2 3 4 3 5 1 5 1 1 1 2 2 2 2 1 3 1 3 2 3 3 3 4
4
1 2 2 1 2 1 1 1 2 1 2 2 1
-1