大样例

题目描述

给你一张 $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

数据范围与约定

本题采用捆绑测试。

对于 $100\%$ 的数据，$3\le n,m\le 5\times 10^5$，$2\le d< n$，保证图中无重边自环。