C++(clang++ 11.0.1) 解法, 执行用时: 160ms, 内存消耗: 9680K, 提交时间: 2022-11-23 13:45:19

#include<bits/stdc++.h>
using namespace std;
const int N = 400010;
int p[N];
int n,m,s,t,ds,dt;
struct node
{
    int x,y,use,w;
    bool operator < (const node &W) const
    {
        return w<W.w;
    }
}e[N];

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        e[i]={u,v,0,0};
    }
    cin>>s>>t>>ds>>dt;
    int dss=0,dtt=0;
    int vals,valt;
    if(ds>dt) vals=1,valt=2;
    else vals=2,valt=1;
    for(int i=1;i<=m;i++)
    {
        e[i].use=0;
        if(e[i].x==s||e[i].y==s) e[i].w=vals;
        if(e[i].x==t||e[i].y==t) e[i].w=valt;
    }
    int cnt=0;
    sort(e+1,e+1+m);
    for(int i=1;i<=m;i++)
    {
        int u=e[i].x,v=e[i].y;
        if(e[i].w==0)
        {
            if(find(u)!=find(v))
            {
                cnt++;
                e[i].use=1;
                p[find(v)]=find(u);
            }
        }
        else
        {
            if(find(u)!=find(v))
            {
                if(u==s||v==s)
                {
                    if(dss==ds) continue;
                    dss++;
                }
                if(v==t||u==t)
                {
                    if(dtt==dt) continue;
                    dtt++;
                }
                cnt++;
                e[i].use=1;
                p[find(v)]=find(u);
            }
        }
    }
    if(dss<=ds&&dtt<=dt&&cnt==n-1)
    {
        cout<<"Yes\n";
        for(int i=1;i<=m;i++)
        {
            if(e[i].use==1)
                cout<<e[i].x<<" "<<e[i].y<<'\n';
        }
    }
    else{
    for(int i=1;i<=n;i++) p[i]=i;
    dss=0,dtt=0;
    int vals,valt;
    if(ds>=dt) vals=1,valt=2;
    else vals=2,valt=1;
    for(int i=1;i<=m;i++)
    {
        e[i].use=0;
        if(e[i].x==s||e[i].y==s) e[i].w=vals;
        if(e[i].x==t||e[i].y==t) e[i].w=valt;
    }
    int cnt=0;
    sort(e+1,e+1+m);
    for(int i=1;i<=m;i++)
    {
        int u=e[i].x,v=e[i].y;
        if(e[i].w==0)
        {
            if(find(u)!=find(v))
            {
                cnt++;
                e[i].use=1;
                p[find(v)]=find(u);
            }
        }
        else
        {
            if(find(u)!=find(v))
            {
                if(u==s||v==s)
                {
                    if(dss==ds) continue;
                    dss++;
                }
                if(v==t||u==t)
                {
                    if(dtt==dt) continue;
                    dtt++;
                }
                cnt++;
                e[i].use=1;
                p[find(v)]=find(u);
            }
        }
    }
         if(dss<=ds&&dtt<=dt&&cnt==n-1)
    {
        cout<<"Yes\n";
        for(int i=1;i<=m;i++)
        {
            if(e[i].use==1)
                cout<<e[i].x<<" "<<e[i].y<<'\n';
        }
    }else cout<<"No"<<endl;
    }
}