730K - Roads Orientation Problem - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=501010;
const int qwq=2003030;

int T;
int n,m,s,t;
int head[N], nxt[qwq], to[qwq],cnt=1;
bool cho[qwq];
int vis[N];
int fa[N],dep[N],lnk[N],son[N];
vector <int> g[N];

void setup() {
	for(int i=1;i<=n;i++) vis[i] = head[i] = dep[i] = fa[i] = lnk[i] = 0, g[i].clear();
	for(int i=1;i<=cnt;i++) nxt[i] = to[i] = cho[i] = 0;
	cnt = 1;
}

void add(int u,int v) {
	nxt[++cnt] = head[u]; head[u] = cnt; to[cnt] = v;
	nxt[++cnt] = head[v]; head[v] = cnt; to[cnt] = u;
}

void DFS(int u,int f) {	fa[u] = f; dep[u] = dep[f] + 1;
	for(int i=head[u];i;i=nxt[i]) {
		int v = to[i];
		if(v==f) continue;
		if(dep[v] && dep[v]<dep[u]) g[son[v]].push_back(i);
		else if(!dep[v]) lnk[v] = i, son[u] = v, DFS(v,u);
	}
}

void search(int u,int cl) {
	int now = u;
	while(!vis[u]) {
		if(cl) cho[lnk[u]^1] = 1;
		else   cho[ lnk[u] ] = 1;
		vis[u] = 1;
		u = fa[u];
	}
	while(now!=u) {
		for(int i=0;i<g[now].size();i++) {
			int e = g[now][i];
			if(cl) cho[ e ] = 1;
			else   cho[e^1] = 1;
			search(to[e^1],cl^1);
		}
		now = fa[now];
	}
}


int main()
{
    int x,y;
    cin>>T;
    while(T--)
    {
        setup();
        cin>>n>>m>>s>>t;
        for(int i=1;i<=m;i++) {
			cin>>x>>y;
			add(x,y);
		}

        DFS(s,0);
        vis[s] = 1;
		search(t,0);

        bool flag = 1;
		for(int i=1;i<=m;i++) {
			if(!cho[i*2] && !cho[i*2+1]) { flag = 0; break; }
		}
        if(!flag) cout<<"No\n";
        else {
			cout<<"Yes\n";
			for(int i=1;i<=m;i++) {
				if(cho[i*2]) cout<<to[i*2+1]<<" "<<to[i*2]<<"\n";
				else         cout<<to[i*2]<<" "<<to[i*2+1]<<"\n";
			}
		}
    }
}/*1693300619.3498464*/