AT_abc469_d.The Big Two

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There is a game with NN players 1,2,…,N1,2,\dots,N.
This game is played in a format where two players face each other one-on-one.
A tournament among the NN players was held MM times, and the two players AmA_m and BmB_m advanced to the final of the mm-th tournament.
Find the number of pairs of integers xx and yy satisfying the following conditions.

  • 1≤x<y≤N1 \leq x \lt y \leq N
  • In every tournament, at least one of players xx and yy advanced to the final.

有 NN 名玩家,编号为 1,2,…,N1,2,\dots,N。
该游戏采用两名玩家一对一进行对抗的形式。
这 NN 名玩家共举行了 MM 次锦标赛,其中第 mm 次锦标赛的决赛选手为玩家 AmA_m 和 BmB_m。
求满足以下条件的整数对 (x,y)(x, y) 的个数:

  • 1≤x<y≤N1 \leq x < y \leq N
  • 在每次锦标赛中,玩家 xx 和 yy 中至少有一人进入了决赛。

输入格式

The input is given from Standard Input in the following format:

NN MM
A1A_1 B1B_1
A2A_2 B2B_2
⋮\vdots
AMA_M BMB_M

输入从标准输入中按以下格式给出:

NN MM
A1A_1 B1B_1
A2A_2 B2B_2
⋮\vdots
AMA_M BMB_M

输出格式

Output the answer in one line.

一行输出答案。

输入输出样例

  • 输入#1

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

    输出#1

    1
  • 输入#2

    7 8
    2 4
    1 3
    1 7
    1 3
    1 2
    1 6
    1 5
    1 3

    输出#2

    2
  • 输入#3

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

    输出#3

    2

说明/提示

Sample 1 Explanation:
The conditions are satisfied when (x,y)=(2,3)(x,y)=(2,3), and not satisfied otherwise.
For example, in the fourth tournament, neither player 11 nor player 44 advanced to the final, so (x,y)=(1,4)(x,y)=(1,4) does not satisfy the conditions.

Sample 2 Explanation:
There are two pairs (x,y)(x,y) satisfying the conditions: (1,2)(1,2) and (1,4)(1,4).

Constraints

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^5
  • 1≤Ai<Bi≤N1 \leq A_i \lt B_i \leq N
  • All input values are integers.

样例 1 解释:
当 (x,y)=(2,3)(x,y)=(2,3) 时,条件满足;其余情况均不满足。
例如,在第四场锦标赛中,选手 11 和选手 44 均未进入决赛,因此 (x,y)=(1,4)(x,y)=(1,4) 不满足条件。

样例 2 解释:
满足条件的数对 (x,y)(x,y) 有两个:(1,2)(1,2) 和 (1,4)(1,4)。

限制条件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^5
  • 1≤Ai<Bi≤N1 \leq A_i \lt B_i \leq N
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页