CF1210D Konrad and Company Evaluation

Konrad 是 VoltModder 公司的人力资源顾问，这是一家大型电气设备生产企业。今天，他的任务是评估公司员工的幸福指数。 公司共有 $n$ 名员工，编号从 $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$。 每天开始时，Konrad 需要统计公司中“危险三元组”的数量。你能帮他完成这个任务吗？

第一行包含两个整数 $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$ 行，每行包含一个整数 $v_i$（$1 \le v_i \le n$），表示在第 $i$ 天结束时，第 $v_i$ 号员工的工资将成为公司最高。

输出 $q+1$ 个整数，第 $i$ 个数表示在第 $i$ 天开始时公司中“危险三元组”的数量。

以第一个样例为例。下图第 $i$ 行表示第 $i$ 天开始时公司的结构。若从 $a$ 指向 $b$ 有一条有向边，表示员工 $a$ 向员工 $b$ 炫耀工资。危险三元组用高亮的边标出。  由 ChatGPT 4.1 翻译