問題文
高桥的秘书渚非常爱他。今天我得盯着高桥君,确保他不会被坏虫附身。
高桥用自己的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
高桥没有朋友,所以他不需要做任何制作。