← 返回题目列表

Codeforces · 1210/D

D. 康拉德和公司评估

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

Konrad 是大型电气设备生产商 VoltModder 的一名人际关系顾问。今天,他的任务是评估公司的幸福程度。

有 $$$n$$$ 人为 VoltModder 工作,编号从 $$$1$$$ 到 $$$n$$$。每个员工在公司赚的钱不同——最初,第 $$$i$$$ 人每天赚 $$$i$$$ 卢布。

在接下来的每一天 $$$q$$$ 中,工资都会进行修改。在第 $$$i$$$ 天结束时,员工 $$$v_i$$$ 将开始每天赚取 $$$n+i$$$ 卢布,并将成为公司收入最高的人。该员工将保留他的新工资,直到再次修改为止。

有些人彼此不喜欢对方。这给公司造成了很大的心理危险。正式来说,如果 $$$a$$$ 和 $$$b$$$ 两个人互相不喜欢,并且 $$$a$$$ 赚的钱比 $$$b$$$ 多,员工 $$$a$$$ 就会向 $$$b$$$ 吹嘘这一点。危险三元组是由三名员工 $$$a$$$、$$$b$$$ 和 $$$c$$$ 组成的三元组,这样 $$$a$$$ 向 $$$b$$$ 吹嘘,$$$b$$$ 又向 $$$c$$$ 吹嘘。如果$$$a$$$ 不喜欢$$$b$$$,那么$$$b$$$ 也不喜欢$$$a$$$。

每天开始时,康拉德需要评估公司中危险三元组的数量。你能帮他做吗?

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$0 \le m \le 100\,000$$$) — 公司中员工的数量以及相互不喜欢的人的数量。以下 $$$m$$$ 行中的每一行都包含两个整数 $$$a_i$$$、$$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \neq b_i$$$) 表示员工 $$$a_i$$$ 和 $$$b_i$$$ 互相讨厌(即 $$$a_i$$$ 不喜欢对方) $$$b_i$$$ 和 $$$b_i$$$ 不喜欢 $$$a_i$$$)。每个这样的关系都会被提及一次。

下一行包含一个整数 $$$q$$$ ($$$0 \le q \le 100\,000$$$) — 工资修改次数。以下 $$$q$$$ 行中的第 $$$i$$$ 行包含一个整数 $$$v_i$$$ ($$$1 \le v_i \le n$$$) 表示在第 $$$i$$$ 天结束时,员工 $$$v_i$$$ 将获得最多收入。

输出

输出 $$$q + 1$$$ 整数。其中第 $$$i$$$ 应包含第 $$$i$$$ 天开始时公司中危险三元组的数量。

示例

输入 #1

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

输出 #1

4
3
2

输入 #2

3 3
1 2
2 3
1 3
5
1
2
2
1
3

输出 #2

1
1
1
1
1
1

注意

考虑第一个样本测试。下图中的第 $$$i$$$ 行显示了第 $$$i$$$ 天开始时的公司结构。从 $$$a$$$ 到 $$$b$$$ 的有向边表示员工 $$$a$$$ 向员工 $$$b$$$ 吹嘘。危险的三元组由突出显示的边缘标记。