C - ソーシャル 解説 /

実行時間制限: 2 sec / メモリ制限: 64 MB

問題文

うさぎが N 匹おり，ボートを使って川を渡ろうとしている．ボートは K 個あり，誰がどのボートに乗るかを適当に決めて乗ることにした．

ところでうさぎというのは互いの仲の良し悪しに敏感であり，狭い空間に仲の悪いうさぎと一緒に閉じ込められると気分を悪くしてしまう． この N 匹のうさぎについても何組かのうさぎは仲が悪いということが分かっており，今の割り当てでは何匹かは気分を悪くしてしまう可能性がある． もっと良い割り当てを考えるのがよいところではあるが，ひとまず今の割り当てで何匹のうさぎが気分を悪くするかを求めて欲しい．

入力形式

入力は以下の形式で与えられる． 

N\ K\\
m1\ bunny1,1\ ...\ bunny1,m1\\
m2\ bunny2,1\ ...\ bunny2,m2\\
...\\
mK\ bunnyK,1\ ...\ bunnyK,mK\\
R\\
p1\ q1\\
...\\
pR\ qR\\

N はボートに乗るうさぎの数である．K はボートの個数である． mi はボート i に乗るうさぎの数である．bunnyi,1, ..., bunnyi,mi はボート i に乗るうさぎの番号 (1 以上 N 以下) を表す． R は仲の悪いうさぎの組の個数を表す． pj, qj はうさぎpj とうさぎ qj の仲が悪いことを表す．

出力形式

気分を悪くするうさぎの数を出力せよ．

制約

  • 1 ≤ N ≤ 50
  • 1 ≤ K ≤ N
  • m1 + ... + mK = N
  • \{bunny1,1, ..., bunny1,m1, bunny2,1, ..., bunnyK,mK \} = \{1, 2, ..., N\}
  • 0 ≤ R ≤ N(N-1)/2
  • 1 ≤ pj < qj ≤ N
  • 組 (pj, qj) は全て異なる．
  • 入力値はすべて整数である．

入出力例

入力例 1

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

出力例 1

0

気分を悪くしているうさぎはいない．

入力例 2

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

出力例 2

3

割り当ては例 1 と同じであるが仲の悪さを表す組が異なっている．この例ではうさぎ 2,3,4 が気分を悪くしてしまう．

入力例 3

10 3
3 4 1 9
3 10 5 2
4 3 8 7 6
9
3 4
1 2
1 9
6 8
1 6
1 8
6 7
6 10
7 8

出力例 3

5
Writer: 楠本充
Tester: 小浜翔太郎

出典

KUPC 2012