← 返回题目列表

AtCoder · abc010_4

D. 预防作弊

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

問題文

高桥的秘书渚非常爱他。今天我得盯着高桥君,确保他不会被坏虫附身。

高桥用自己的SNS与女孩相处。在 SNS 上关注您的好友,并向您找到的女孩发送消息。 渚决定操纵这个SNS,让女孩们看不到高桥君的消息。

可以进行以下手工活动: 2一。

  • 解除两个特定人之间的友谊
  • 更改特定人员的密码并使其无法登录 Takahashi 的密码无法更改。 (21:11 补充)

一旦友谊解除,高桥将无法再追查两人之间的关系。但是,如果可以通过其他朋友追踪该信息,则不适用。

如果您更改密码,该人将无法再看到您的消息。由于好友关系保持不变,因此可以追踪密码被更改的人并寻找其他好友。

渚酱想尽可能地减少操作次数,让提前标记过她的女孩们看不到高桥君的消息。求渚需要做这件事的次数。


入力

输入是按以下格式从标准输入给出的。

N G E
p_1 p_2 ... p_G
a_1 b_1
a_2 b_2
:
a_E b_E
  • 1 行包含一个整数,表示 SNS 的注册用户数。 N (1 ≦ N ≦ 100) 以及凪咲标记的女孩数量 G (0 ≦ G ≦ N - 1),表示 SNS 好友数量的整数 E (0 ≦ E ≦ N × (N-1) / 2)用空格分隔。 在
  • 2 行中,渚酱已经标记了它。 代表第 i 个女孩 ID 的整数 p_i (1 ≦ p_i ≦ N - 1) 值由空格分隔。 给出了 G 。 来自行
  • 3 在 E 行中,给出了有关友谊的信息。其中 行 i 代表第 i 条好友关系中两个人的ID号 2 整数 a_i (0 ≦ a_i ≦ N - 1) b_i (0 ≦ b_i ≦ N - 1) 值以空格分隔。 当
  • i ≠ j 时,a_i = a_j 和 b_i = b_j,或 a_i = b_j 和 b_i = a_j 保证不会发生。
  • 在所有输入中,高桥的 ID 为 0 有保证。 如果您正确回答了满足

部分点

0 ≦ E ≦ 12 的测试用例,您将获得部分分数。 99 点。

出力

渚酱需要做的最少次数是 输出为 1 行。在输出末尾添加换行符。


入力例1

4 2 3
2 3
0 1
1 2
1 3

出力例1

1

如图所示, 1 仅仅通过解除一份友谊,2 你可以将其他女孩与高桥分开。


入力例2

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

出力例2

1

由于只有一名女孩被标记,您只需禁止此人登录即可实现您的目标。


入力例3

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

出力例3

2

通过执行如图所示的工艺,您可以为所有女孩制作工艺。


入力例4

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

出力例4

2

ID 是 请注意,禁用 3 人登录不会影响 Takahashi 寻找朋友的能力。


入力例5

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

出力例5

0

高桥没有朋友,所以他不需要做任何制作。