题目描述

经过元旦联欢会的多项活动后，$n$ 名同学（编号从 1 到 $n$）都获得了一些积分，凑巧的是，第 $i$ 个同学的积分就是 $i$ 分。在接下来的 $q$ 个联欢项目中，每个项目都会增加一位同学的积分，具体来说，在第 $j(1 \leq j \leq q)$ 个项目结束后，第 $v_j$ 号同学的积分将变为 $n+j$ 分（因此暂时成为班里积分最高的人），该同学会一直保持新的积分，直到下一次该同学的积分被再次调整。

有些同学之间经常彼此聊天，这可能会导致发生炫耀事件。具体来说，如果两个人 $a$ 和 $b$ 彼此聊天，并且 $a$ 的积分比 $b$ 高，那么 $a$ 会向 $b$ 炫耀自己的积分。一个“炫耀三元组”指的是三位学生 $a$、$b$ 和 $c$ 满足 $a$ 会向 $b$ 炫耀、$b$ 会向 $c$ 炫耀。

老师不喜欢班里有太多同学互相炫耀，因此拜托你统计每个活动前后“炫耀三元组”的总数量。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 100000$，$0 \leq m \leq 100000$），分别表示同学人数和彼此聊天的关系对数。

接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i(1 \leq a_i < b_i \leq n)$，表示学生 $a_i$ 和 $b_i$ 彼此聊天，每对关系只会出现一次。注意彼此聊天不具有传递性（即 $X$ 和 $Y$ 彼此聊天、$Y$ 和 $Z$ 彼此聊天不代表 $X$ 和 $Z$ 一定彼此聊天）。

接下来一行包含一个整数 $q(0 \leq q \leq 100000)$，表示联欢项目的个数。接下来的 $q$ 行，每行包含一个整数 $v_j(1 \leq v_j \leq n)$，表示在第 $j$ 个联欢项目结束时，第 $v_j$ 号学生的积分将成为班级最高。

输出格式

输出 $q+1$ 个整数，第 $i$ 个数表示在第 $i-1$ 个项目后班级中“炫耀三元组”的数量。注意输出的第一个数字是初始时的“炫耀三元组”数量。

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

4
3
2

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

1
1
1
1
1
1

提示

数据范围：

对于前 $30\%$ 的数据，满足 $n,q \le 500$；

对于另外 $20\%$ 的数据，满足 $q=0$；

对于 $100\%$ 的数据，满足“输入格式”中给出的数据范围。