#P10494. [2021年联测]youngxanthoushost

    ID: 9611 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-容斥原理三元环计数四元环计数按度数定向时间戳避免清空数组

[2021年联测]youngxanthoushost

题目描述

给定一个有 nn 个点的完全图,其中 mm 条边是红色,其他边都是蓝色。

设 fredf_{\mathrm{red}} 为从图中选择四个不同的点,使它们之间的六条边都是红色的方案数。设 fbluef_{\mathrm{blue}} 为六条边都是蓝色的方案数。选择的四个点不计顺序。

求 ∣fred−fblue∣|f_{\mathrm{red}}-f_{\mathrm{blue}}|。

输入格式

第一行两个整数 n,mn,m,分别表示点数和红边数。接下来 mm 行,每行两个整数 x,yx,y,表示一条红边。点编号为 11 到 nn。

输出格式

一行一个整数,表示答案。

样例

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

数据范围

n≤105n\le10^5,m≤2×105m\le2\times10^5。

原赛子任务 特殊限制 原赛分值
1 n≤100n\le100 10
2 n≤500n\le500,m≤1000m\le1000
3 n≤500n\le500
4 n≤3000n\le3000,m≤6000m\le6000 25
5 n≤3000n\le3000
6 n≤40000n\le40000,m≤80000m\le80000 15
7 n≤100000n\le100000,m≤200000m\le200000 5

原 PDF 题面