← 返回题目列表

AtCoder · abc402_d

G. 越线

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有 N 圆上等距点,顺时针标记为 1,2,\ldots,N.

有 M 不同 行,其中 i第一条线穿过两个不同的点 A_i 和 B_i (1 \leq i \leq M).

查找对的数量 (i,j) 满足:

  • 1 \le i < j \le M,和
  • 这 i-th 和 自记录开始以来,第 j第条线相交。

约束

  • 2 \leq N \leq 10^6
  • 1 \leq M \leq 3 \times 10^{5}
  • 1 \leq A_i < B_i \leq N (1 \leq i \leq M)
  • (A_i,B_i) \neq (A_j,B_j) (i \neq j)
  • 所有输入值均为整数。

输入

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

输出

打印答案。


示例输入 1

8 3
1 5
1 8
2 4

示例输出 1

2

如下图所示,圆上有八个点和三条线。

第 1 条线和第 2 条线相交。第 1 条线和第 3 条线不相交。第 2 条线和第 3 条线相交。自从成双成对 (i,j)=(1,2),(2,3) 满足条件,打印 2.


示例输入 2

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

示例输出 2

40