問題文

$0, 1, \cdots, N, N + 1$ の $N + 2$ 頂点をもつ有向グラフ上の、端点以外頂点素な $0(N+1)$ パス集合 $\mathcal{P} = \{P_1, \cdots, P_X\}, \mathcal{Q} = \{Q_1, \cdots, Q_Y\}$ が与えられます。$1 \le i \le X$ に対して、$P_i$ に含まれる辺の数は $K_i$ 本で、$j$ 番目の頂点（$0$ 番目の頂点から始まるとします）は $u_{i, j}$ です。また、$1 \le i \le Y$ に対して、$Q_i$ に含まれる辺の数は $L_i$ 本で、$j$ 番目の頂点（$0$ 番目の頂点から始まるとします）は $v_{i, j}$ です。ここで、$\mathcal{P}$ のパスと $\mathcal{Q}$ のパスは共通の辺をもたないものとします。ただし、$\mathcal{P}$ のパスと $\mathcal{Q}$ のパスの間に平行辺が存在することはあり得ます（すなわち、ある $2$ 頂点 $u, v$ に対して、$u$ から $v$ への辺が $\mathcal{P}$ と $\mathcal{Q}$ のどちらにも含まれていることはあり得ますが、これらは別の辺として扱います）。更に、$\mathcal{P}, \mathcal{Q}$ のすべてのパスの長さは $2$ 以上であるものとします。

これらの $\mathcal{P}, \mathcal{Q}$ から、あなたは以下を満たすパス集合 $\mathcal{R}$ を構成したいと思いました。

• $\mathcal{R}$ は端点以外頂点素な $0(N+1)$ パス集合。
• 各 $R \in \mathcal{R}$ に対して $R$ 上のある頂点 $u$ が存在し，$R$ の $u$ 以前の辺は $E(\mathcal{P})$ に含まれ，$u$ 以降の辺は $E(\mathcal{Q})$ に含まれる。
• 各 $P \in \mathcal{P}$ に対して，$P$ の始辺は $E(\mathcal{R})$ に含まれる。
• 各 $Q \in \mathcal{Q}$ に対して，$Q$ の終辺は $E(\mathcal{R})$ に含まれる。

ただし、パス集合 $\mathcal{X}$ に対して、$E(\mathcal{X})$ は $\mathcal{X}$ のどれかのパスに含まれる辺全体の集合とします。

このような $\mathcal{R}$ が存在するか判定し、存在するならば $|E(\mathcal{P}) \cap E(\mathcal{R})|$ が最大となるときの値を求めてください。

入力

$N \ X \ Y$
$K_1$
$u_{1,0} \ u_{1,1} \ \cdots \ u_{1, K_1}$
$\vdots$
$K_X$
$u_{X,0} \ u_{X,1} \ \cdots \ u_{X, K_X}$
$L_1$
$v_{1,0} \ v_{1,1} \ \cdots \ v_{1, L_1}$
$\vdots$
$L_Y$
$v_{Y,0} \ v_{Y,1} \ \cdots \ v_{Y, L_Y}$

• 入力される値はすべて整数
• $1 \le N \le 10^5$
• $1 \le X, Y \le N$
• $2 \le K_i \le N + 1$
• $u_{i,0} = 0$ かつ $u_{i,K_i} = N + 1$
• $1 \le j < K_i$ に対して、$1 \le u_{i,j} \le N$
• $1 \le j < K_i, 1 \le j' < K_{i'}$ に対して、$i \neq i'$ または $j \neq j'$ ならば $u_{i,j} \neq u_{i', j'}$
• $2 \le L_i \le N + 1$
• $v_{i,0} = 0$ かつ $v_{i,L_i} = N + 1$
• $1 \le j < L_i$ に対して、$1 \le v_{i,j} \le N$
• $1 \le j < L_i, 1 \le j' < L_{i'}$ に対して、$i \neq i'$ または $j \neq j'$ ならば $v_{i,j} \neq v_{i', j'}$

出力

条件を満たすパス集合 $\mathcal{R}$ が存在するとき、$|E(\mathcal{P}) \cap E(\mathcal{R})|$ の最大値を出力してください。そうでないとき、$-1$ を出力してください。

サンプル

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

4

2 1 1
2
0 1 3
2
0 2 3

2

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

4

19 3 3
4
0 1 2 3 20
8
0 4 5 6 7 8 9 10 20
4
0 11 12 13 20
6
0 14 3 15 8 16 20
5
0 17 2 9 18 20
4
0 19 12 7 20

10