大样例
题目描述
给你一张 $n$ 个点，$m$ 条边的无向图与一个整数 $d$，求有多少个大小为 $3$ 的连通块使得其中点的编号的极差小于等于 $d$。
两个连通块不同当且仅当一个连通块内有某个点 $x$ 而另一个连通块里没有。
输入格式
第一行三个整数 $n,m,d$。
接下来 $m$ 行每行两个整数 $u,v$，表示图中有一条边 $(u,v)$。
输出格式
一行一个整数表示答案。
样例 #1
样例输入 #1
4 5 3
1 2
2 3
2 4
1 3
3 4样例输出 #1
4样例 #2
样例输入 #2
6 6 3
1 4
4 3
3 2
2 5
1 2
2 6样例输出 #2
5数据范围与约定
本题采用捆绑测试。
| 子任务编号 | $n,m\le $ | 特殊限制 | 分值 |
|---|---|---|---|
| $1$ | $500$ | 无 | $10$ |
| $2$ | $10^4$ | 无 | $10$ |
| $3$ | $5\times 10^5$ | 图为菊花图 | $10$ |
| $4$ | $5\times 10^5$ | $d=n-1$ | $20$ |
| $5$ | $5\times 10^5$ | 图为二分图 | $20$ |
| $6$ | $5\times 10^5$ | 无 | $30$ |
对于 $100\%$ 的数据，$3\le n,m\le 5\times 10^5$，$2\le d< n$，保证图中无重边自环。