分数: 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