← 返回题目列表

AtCoder · kupc2012_3

C. 社交

中文机器翻译题面 查看原题

問題文

兔子 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

作者:楠本满
测试员:奥巴马正太郎