分组
题号：NC218218
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

你有一张 n 个点的有向图，我们定义一个有向图的重量是该图内所有强连通分量大小（即其节点数量）的平方和。

有 m 条边，依次编号为 1,2,…,m。现在需要将其分成若干组，满足：


  1. 每一组内边的编号连续；
  2. 对于每一组边，将其加入原图内得到 G，需要满足 G 的重量不能超过 k，其中 k 是给定的阈值。


请求出最小分组的数量。

输入描述:

一行三个整数 n,m,k，分别表示图中节点数，给出的边数和阈值的大小；
接下来 m 行，每行两个整数 u,v，表示一条从 u 到 v 的有向边。

输出描述:

一行一个整数，表示最小分组的数量。
示例1

输入

复制 
6 12 8
1 2
2 3
3 4
3 2
3 1
4 1
4 5
1 5
6 5
5 6
3 6
6 3

输出

复制 
3

备注:

对于100%的数据，保证 ，图中可能存在重边和自环。