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$$$ 吹嘘。危险的三元组由突出显示的边缘标记。