#P17209. [2025年南外]四元组

    ID: 16368 传统题 500ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-容斥原理交换求和顺序按度数定向三元环计数四元环计数稀疏状态重置

[2025年南外]四元组

Description

给你一个nn个点的完全图,其中有mm条边是红色,其它边是蓝色

记f红色f_{红色}表示四元组(i,j,k,l)(i,j,k,l)的个数使得四个点之间所有边都是红色

记f蓝色f_{蓝色}表示四元组(i,j,k,l)(i,j,k,l)的个数使得四个点之间所有边都是蓝色

求f红色−f蓝色f_{红色}-f_{蓝色}的绝对值

Input Format

第一行两个整数nn,mm表示点数和红色边数

接下来每行两个整数xx,yy表示一条红色边

Output Format

一行一个整数表示答案

Sample

input

7 6
1 2
1 3
1 4
2 3
2 4
3 4

output

3

Hint

对于所有数据,n≤105n \leq10^5,m≤2∗105m \leq2*10^5

subtask1(10pts)subtask1(10pts):n≤100n \leq100

subtask2(10pts)subtask2(10pts):n≤500,m≤1000n \leq500,m \leq1000

subtask3(10pts)subtask3(10pts):n≤500n \leq500

subtask4(25pts)subtask4(25pts):n≤3000,m≤6000n \leq3000,m \leq6000

subtask5(25pts)subtask5(25pts):n≤3000n \leq3000

subtask6(15pts)subtask6(15pts):n≤40000,m≤80000n \leq40000,m \leq80000

subtask7(5pts)subtask7(5pts):n≤100000,m≤200000n \leq100000,m \leq200000