D题
因为细节错误,最后一分钟才A出来。。。。。。。

首先,我们有一个很明显的贪心。
就是,我们从左到右去枚举边的话,肯定是尽量囊括边 到濒临阈值的情况下

即,我们从最左端一直向右取边,取到极限,算作一组
然后以当前位置为最左端,向右取边取到极限,算作一组
以此类推。

但是我们是无法这样做的,因为我们无法做到动态的查询强连通分量

那么二分可不可以呢?
首先我们以最左端编号1开始二分,找到他可以取到的最右端的编号l2
然后再次二分。。。。
每次二分都使用一次tajan算法验证一遍

但是这样行不行呢?
没试,但是预计会T 我们可以大致感觉到这个复杂度是有点高的

这时,我看了下数据

然后我们可以意识到一个重要的结论:
如果我这个图中只有n个点,那么这个图的重量一定是<=n^2的!!!!
即,我这些点连成了一个强连通

这个结论扩展到边也差不多
如果这个图有m个边,n个点。那么这个图的重量一定是<=m^2 + n-m !!!!!
即,我m条边构造了一个有m个点的强连通分量,然后剩余n-m个孤立的点!!

一句这个结论我们可以做到什么?
这说明了,我们在一开始就可以按照结论,将整个边序列分成大致 个区间!!!!

然后我们需要考虑的就变成了:
从最左边开始,一个一个地合并区间!
能合并就合并,无法合并就取最右(依照我们之前的贪心策略,我们要尽量包含多的边取到上限!)

而这里,如何找到最右边的那个上限,我们就可以使用二分了!

当然,为了不T我们还需要,稍微修改一下tarjan,中遍历点的情况
即:我们只要保留我们所选区间的点即可。
具体实现见代码:

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
using namespace std;
typedef long long ll;
const int max_n = 1e6+100;
int n,m;
ll k;
int es[max_n][2];
vector<int> V;
struct edge
{
    int to,next;
}E[max_n<<1];
int head[max_n];
int cnt=1;
void add(int from,int to)
{
    E[cnt].to=to;
    E[cnt].next=head[from];
    head[from]=cnt++;
}

int dfn[max_n],low[max_n];
stack<int> st;
int colour=0;
int color[max_n];
int sz[max_n<<1];
int tot=0;
void tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    st.push(u);
    for (int i = head[u];i;i = E[i].next)
    {
        int v = E[i].to;
        if (!dfn[v]) 
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (color[v] == 0)low[u] = min(low[u], dfn[v]);
    }
    if (low[u] != dfn[u])return;

    colour++;
    while (st.top() != u) 
    {
        color[st.top()] = colour;
        st.pop();
        sz[colour]++;
    }
    color[st.top()] = colour;
    st.pop();
    sz[colour]++;
}


int que[max_n];
int h=0;
int cct=0;
int vis[max_n];
bool check(int l,int r)
{
    ++cct;
    int nodes = 0;
    h=0;
    for (int i=l;i<=r;++i)
    {
        que[++h]=es[i][0];
        que[++h]=es[i][1];
        if (vis[es[i][0]]!=cct)
        {
            vis[es[i][0]]=cct;
            ++nodes;
        }
        if (vis[es[i][1]]!=cct)
        {
            vis[es[i][1]]=cct;
            ++nodes;
        }
    }
    nodes = n-nodes;
    cnt=1;
    for (int i=1;i<=h;++i)head[que[i]]=dfn[que[i]]=low[que[i]]=color[que[i]]=0;
    for (int i=l;i<=r;++i)add(es[i][0],es[i][1]);

    ll ans = 0;
    tot=0;
    colour=0;
    for (int i=0;i<=h;++i)sz[i]=0;
    while (!st.empty())st.pop();

    for (int i=1;i<=h;++i)
    {
        if (dfn[que[i]])continue;
        tarjan(que[i]);
    }

    for (int i=1;i<=colour;++i)
        ans+= (ll)sz[i]*(ll)sz[i];

    return ans+nodes<=k;
}

int Solve(int cur,int l,int r)
{
//    cout<<cur<<" "<<l<<" "<<r<<endl;
    --r;
    if (check(cur,r))return cur;
    int ans=l-1;
    int lft = l-1,rgt=r;
    while (lft<=rgt)
    {
        int mid = (lft+rgt)>>1;
        if (check(cur,mid))
        {
            lft = mid+1;
            ans = mid;
        }
        else rgt =mid-1;
    }
    ++ans;
    if (ans==r+1)return cur;
    else return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m>>k;
    for (int i=1;i<=m;++i)cin>>es[i][0]>>es[i][1];
    V.push_back(1);
    ll lim = sqrt(k);
    while (lim*lim+n-lim>k)--lim;
    for (int i=2;i<=m;++i)
        if (i-V.back()==lim)
            V.push_back(i);

    if (V.size()==1)
    {
        cout<<1<<endl;
        return 0;
    }

    else if (V.size()==2)
    {
        if (check(1,m))cout<<1<<endl;
        else cout<<2<<endl;
        return 0;
    }

    int ans = 1;
    V.push_back(m+1);
    int cur = 1;

    for (int i=1;i<V.size()-1;++i)
    {
        int pre = cur;
        cur = Solve(cur,V[i],V[i+1]);
        if (cur!=pre)++ans;
    }
    cout<<ans<<endl;
}