logo AlgoBeat OnlineJudge
登录 注册

#214979. [海淀区普及组 2025 T3] 炫耀预警器

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

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

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

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

输入格式

第一行包含两个整数 ),分别表示同学人数和彼此聊天的关系对数。

接下来的 行,每行包含两个整数 ,表示学生 彼此聊天,每对关系只会出现一次。注意彼此聊天不具有传递性(即 彼此聊天、 彼此聊天不代表 一定彼此聊天)。

接下来一行包含一个整数 ,表示联欢项目的个数。接下来的 行,每行包含一个整数 ,表示在第 个联欢项目结束时,第 号学生的积分将成为班级最高。

输出格式

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

样例

样例输入 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

数据范围与提示

数据范围:

对于前 的数据,满足

对于另外 的数据,满足

对于 的数据,满足“输入格式”中给出的数据范围。