思路

显然，答案肯定是割边。

tarjan 求出所有割边，在 tarjan 的 dfs 的时候维护出此节点的子树中服务 A 和服务 B 的数量。

如果此子树中并不包含服务 A 或者服务 B ，或者包含了全部服务 A 或者服务 B，那么这个点到这个子树的边即为一条关键边。

此题搬运的时候没有搬运 spj……所以这个代码暂时过不了。

代码

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005],dfn[100005],low[100005],cnt,ans,tot,n,m,l,k;
vector<int> v[100005];
vector<int> ans1,ans2;
void tarjan(int u,int fa){//tarjan模板
    dfn[u]=low[u]=++tot;
    for(int nv:v[u]){//C++11语法，遍历子节点
        if(!dfn[nv]){//找到割边
            tarjan(nv,u);
            low[u]=min(low[u],low[nv]);
            if(low[nv]>dfn[u]){
                if(!a[nv]||!b[nv]||a[nv]==l||b[nv]==k){//没有A/B，或者A/B全在子树
                    ans++;ans1.push_back(nv);ans2.push_back(u);
                }
            }
            a[u]+=a[nv],b[u]+=b[nv];
        }
        if(nv!=fa){
            low[u]=min(low[u],dfn[nv]);
        }
    }
}
int main(){
    cin>>n>>m>>l>>k;
    for(int i=1;i<=l;i++){int tmp;cin>>tmp;a[tmp]=1;}
    for(int i=1;i<=k;i++){int tmp;cin>>tmp;b[tmp]=1;}
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        v[a].push_back(b);v[b].push_back(a);
    }
    tarjan(1,0);
    cout<<ans<<endl;
    for(int i=0;i<ans;i++) cout<<ans1[i]<<' '<<ans2[i]<<endl;
    return 0;
}