ACM ICPC 2017–2018, NEERC – Northern Eurasia Finals C conection

链接：Gym - 101630C，动动手指打开你的codeforce.com就可，反正也没人看（->_->)
题意：留下2n条边，使所有点都相互联通
思路：建正边和反边，均和你随机选择的一个点在两张图中和任一点联通即可，两遍dfs，这个正反边在kuangbin最短路专题中有。
然后因为链式前向星的存图方式正好可以标记边，直接标记即可。

哦对忘了说了，t组数据要清空，要清空！！！
然后就是最爱的代码环节

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+9;
int ver[maxn],Next[maxn],head[maxn];
int tot;int n,m;
struct node
{
    int l,r;
}edge[maxn];
void add(int x,int y)
{
    ver[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
int ver1[maxn],Next1[maxn],head1[maxn];
int tot1;
void add1(int x,int y)
{
    ver1[++tot1]=y;
    Next1[tot1]=head1[x];
    head1[x]=tot1;
}
bool book[maxn];///标记边
int vis[maxn],vis1[maxn];
void dfs(int x)
{
    vis[x]=1;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(vis[y])continue;
        book[i]=1;
        dfs(y);
    }
}
void dfs1(int x)
{
    vis1[x]=1;
// cout<<"dfs="<<x<<endl;
    for(int i=head1[x];i;i=Next1[i])
    {
        int y=ver1[i];
        if(vis1[y])continue;
        book[i]=1;
        dfs1(y);
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(head,0,sizeof head);
        memset(head1,0,sizeof head1);
        memset(book,0,sizeof book);
        memset(vis,0,sizeof vis);
        memset(vis1,0,sizeof vis1);
        tot=0,tot1=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add(u,v);
            add1(v,u);
            edge[i].l=u;
            edge[i].r=v;
// cout<<i<<" "<<tot<<" "<<tot1<<endl;
        }
        dfs(1);
        dfs1(1);
        int num=m-2*n;
        for(int i=1;i<=m;i++)
        {
// cout<<"i=="<<book[i]<<endl;
            if(!book[i])
            {
                printf("%d %d\n",edge[i].l,edge[i].r);
                num--;
            }
            if(num==0)break;
        }
// cout<<endl;
// for(int i=1;i<=n;i++)
// cout<<vis[i]<<" "<<vis1[i]<<endl;
    }


}