Problem: One-Way Conveyors

You are working at a factory manufacturing many different products. Products have to be processed on a number of different machine tools. Machine shops with these machines are connected with conveyor lines to exchange unfinished products. Each unfinished product is transferred from a machine shop to another through one or more of these conveyors.

As the orders of the processes required are not the same for different types of products, the conveyor lines are currently operated in two-way. This may induce inefficiency as conveyors have to be completely emptied before switching their directions. Kaizen (efficiency improvements) may be found here!

Adding more conveyors is too costly. If all the required transfers are possible with currently installed conveyors operating in fixed directions, no additional costs are required. All the required transfers, from which machine shop to which, are listed at hand. You want to know whether all the required transfers can be enabled with all the conveyors operated in one-way, and if yes, directions of the conveyor lines enabling it.

Input

The input consists of a single test case of the following format.


$n$ $m$
$x_1$ $y_1$
.
.
.
$x_m$ $y_m$
$k$
$a_1$ $b_1$
.
.
.
$a_k$ $b_k$


The first line contains two integers $n$ ($2 \leq n \leq 10 000$) and $m$ ($1 \leq m \leq 100 000$), the number of machine shops and the number of conveyors, respectively. Machine shops are numbered $1$ through $n$. Each of the following $m$ lines contains two integers $x_i$ and $y_i$ ($1 \leq x_i < y_i \leq n$), meaning that the $i$-th conveyor connects machine shops $x_i$ and $y_i$. At most one conveyor is installed between any two machine shops. It is guaranteed that any two machine shops are connected through one or more conveyors. The next line contains an integer $k$ ($1 \leq k \leq 100 000$), which indicates the number of required transfers from a machine shop to another. Each of the following $k$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i \leq n$, $1 \leq b_i \leq n$, $a_i \ne b_i$), meaning that transfer from the machine shop $a_i$ to the machine shop $b_i$ is required. Either $a_i \ne a_j$ or $b_i \ne b_j$ holds for $i \ne j$.

Output

Output “No” if it is impossible to enable all the required transfers when all the conveyors are operated in one-way. Otherwise, output “Yes” in a line first, followed by $m$ lines each of which describes the directions of the conveyors. All the required transfers should be possible with the conveyor lines operated in these directions. Each direction should be described as a pair of the machine shop numbers separated by a space, with the start shop number on the left and the end shop number on the right. The order of these $m$ lines do not matter as far as all the conveyors are specified without duplicates or omissions. If there are multiple feasible direction assignments, whichever is fine.

Sample Input 1


3 2
1 2
2 3
3
1 2
1 3
2 3


Sample Output 1


Yes
1 2
2 3


Sample Input 2


3 2
1 2
2 3
3
1 2
1 3
3 2


Sample Output 2


No


Sample Input 3


4 4
1 2
1 3
1 4
2 3
7
1 2
1 3
1 4
2 1
2 3
3 1
3 2


Sample Output 3


Yes
1 2
2 3
3 1
1 4






Example

Input

3 2
1 2
2 3
3
1 2
1 3
2 3


Output

Yes
1 2
2 3

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 10005

struct Edge{
	Edge(){
		s = t = 0;
		index = 0;
	}
	Edge(int arg_s,int arg_t,int arg_index){
		s = arg_s;
		t = arg_t;
		index = arg_index;
	}
	bool operator<(const struct Edge &arg) const{
		if(s != arg.s){
			return s < arg.s;
		}else{
			return t < arg.t;
		}
	}
	int s,t,index;
};

struct Info{
	Info(int arg_to,int arg_edge_id){
		to = arg_to;
		edge_id = arg_edge_id;
	}
	int to,edge_id;
};

struct Data{
	int start,goal;
};

struct Bridge{

	int a,b;
};

struct Edge2{
	Edge2(int arg_from,int arg_to){
		from = arg_from;
		to = arg_to;
	}
	int from,to;
};

int V,E,number;
int table[SIZE],num_UP[SIZE],num_DOWN[SIZE];
int order[SIZE],lowlink[SIZE];
int height[SIZE],boss[SIZE],num_out[SIZE];
int root; //根ノードの番号
int MAX_LOG_V = 16;
int num_group;
int POW[17];
int PARENT[16][SIZE],DEPTH[SIZE];
bool visited[10*SIZE],is_bridge[10*SIZE],check[SIZE];
Edge edge[10*SIZE];
Data data[10*SIZE];
Bridge bridge[10*SIZE];
map<int,int> MAP;
map<int,bool> WENT[SIZE];
vector<Info> G[SIZE];
vector<int> Group_G[SIZE];
vector<Edge2> ANS;


//ボスIDと木ノードindexの対応付け
int getGroupIndex(int boss_id){

	auto at = MAP.find(boss_id);

	if(at == MAP.end()){

		MAP[boss_id] = num_group++;
	}
	return MAP[boss_id];
}

int find(int x){
	if(x == boss[x])return x;
	else{
		return boss[x] = find(boss[x]);
	}
}

bool isSame(int x,int y){
	return find(x) == find(y);
}

void unite(int x,int y){
	x = find(x);
	y = find(y);

	if(x == y)return;

	if(height[x] < height[y]){
		boss[x] = y;
	}else{
		boss[y] = x;
		if(height[x] == height[y])height[x]++;
	}
}

void recursive(int node_id){

	order[node_id] = number++;
	lowlink[node_id] = order[node_id];

	int next_node;

	for(int i = 0; i < G[node_id].size(); i++){
		next_node = G[node_id][i].to;

		if(order[next_node] == -1){ //頂点next_nodeをまだ訪れていない

			visited[G[node_id][i].edge_id] = true;
			recursive(next_node);
			lowlink[node_id] = min(lowlink[node_id],lowlink[next_node]);

		}else if(visited[G[node_id][i].edge_id] == false){ //後退辺をまだ通っていない場合
			lowlink[node_id] = min(lowlink[node_id],order[next_node]);
		}
	}
}

//PARENTとDEPTHを再帰的に設定
void dfs(int node_id,int parent_id,int d){
	PARENT[0][node_id] = parent_id;
	DEPTH[node_id] = d;
	for(int i = 0; i < Group_G[node_id].size(); i++){
		if(Group_G[node_id][i] != parent_id){
			dfs(Group_G[node_id][i],node_id,d+1);
			num_out[node_id]++;
		}
	}
}

//初期化
void init(){
	//parent[0]とdepthを初期化する
	dfs(root,-1,0);
	//parentを初期化する
	for(int k = 0; k + 1 < MAX_LOG_V; k++){
		for(int node_id = 0; node_id < V; node_id++){
			if(PARENT[k][node_id] < 0)PARENT[k+1][node_id] = -1; //node_idの2^k上のノードがルートノードより上なら、2^(k+1)上も同様とする
			else{
				PARENT[k+1][node_id] = PARENT[k][PARENT[k][node_id]];
			}
		}
	}
}


int lca(int left,int right){

	if(DEPTH[left] > DEPTH[right])swap(left,right);

	for(int k = MAX_LOG_V-1; k >= 0; k--){
		if(DEPTH[right]-DEPTH[left] >= POW[k]){
			right = PARENT[k][right];
		}
	}

	if(left == right)return left;

	for(int k = MAX_LOG_V-1; k >= 0; k--){
		if(PARENT[k][left] == PARENT[k][right]){
			//Do nothing
		}else{
			left = PARENT[k][left];
			right = PARENT[k][right];
		}
	}
	return PARENT[0][left];
}

void makeEdge(int node_id,int parent){

	check[node_id] = true;
	for(int i = 0; i < G[node_id].size(); i++){

		if(is_bridge[G[node_id][i].edge_id])continue;

		int next = G[node_id][i].to;
		if(next == parent)continue;

		auto at = WENT[next].find(node_id);
		if(at != WENT[next].end())continue;

		ANS.push_back(Edge2(node_id,next));

		WENT[node_id][next] = true;
		if(check[next])continue;

		makeEdge(next,node_id);
	}
}

int main(){

	POW[0] = 1;
	for(int i = 1; i <= MAX_LOG_V; i++){

		POW[i] = POW[i-1]*2;
	}

	int N;
	scanf("%d %d",&N,&E);

	for(int i = 0; i < E; i++){
		scanf("%d %d",&edge[i].s,&edge[i].t);

		edge[i].s--;
		edge[i].t--;
		edge[i].index = i;

		if(edge[i].s > edge[i].t){
			swap(edge[i].s,edge[i].t);
		}

		G[edge[i].s].push_back(Info(edge[i].t,i));
		G[edge[i].t].push_back(Info(edge[i].s,i));
	}

	int K;
	scanf("%d",&K);

	for(int i = 0; i < K; i++){

		scanf("%d %d",&data[i].start,&data[i].goal);
		data[i].start--;
		data[i].goal--;
	}

	sort(edge,edge+E);

	number = 0;

	for(int i = 0; i < N; i++){
		order[i] = -1;
		lowlink[i] = -1;
	}

	for(int i = 0; i < E; i++){
		visited[i] = false;
	}

	recursive(0);

	int from,to;

	for(int i = 0; i < E; i++){

		is_bridge[i] = false;
	}

	int num_bridge = 0;

	//橋の特定
	for(int i = 0; i < E; i++){

		from = edge[i].s;
		to = edge[i].t;

		if(order[edge[i].s] > order[edge[i].t]){
			swap(from,to);
		}

		if(order[from] < lowlink[to]){
			bridge[num_bridge].a = from;
			bridge[num_bridge].b = to;

			num_bridge++;
			is_bridge[edge[i].index] = true; //★★★★注意★★★★
		}
	}

	for(int i = 0; i < N; i++){

		boss[i] = i;
		height[i] = 0;
	}

	for(int i = 0; i < E; i++){
		if(is_bridge[edge[i].index]){
			continue;
		}

		unite(edge[i].s,edge[i].t);
	}


	num_group = 0;

	//グループ間のエッジを張る
	for(int i = 0; i < num_bridge; i++){

		Group_G[getGroupIndex(find(bridge[i].a))].push_back(getGroupIndex(find(bridge[i].b)));
		Group_G[getGroupIndex(find(bridge[i].b))].push_back(getGroupIndex(find(bridge[i].a)));
	}

	//LCA木を作る
	root = 0;
	V = num_group;

	for(int i = 0; i < V; i++){

		num_out[i] = 0;
	}

	init();

	for(int i = 0; i < V; i++){

		num_UP[i] = 0;
		num_DOWN[i] = 0;
	}

	for(int i = 0; i < K; i++){

		int start = getGroupIndex(find(data[i].start));
		int goal = getGroupIndex(find(data[i].goal));

		if(start == goal)continue; //同じ連結成分は無視

		int mid = lca(start,goal);

		if(start == mid){

			num_DOWN[goal]++;
			num_DOWN[start]--;

		}else if(goal == mid){

			num_UP[start]++;
			num_UP[goal]--;

		}else{ //start != mid && goal != mid

			num_UP[start]++;
			num_UP[mid]--;
			num_DOWN[goal]++;
			num_DOWN[mid]--;
		}
	}

	//上り&下りの数を計算
	queue<int> Q;
	for(int i = 0; i < V; i++){
		if(num_out[i] == 0){
			Q.push(i);
		}
	}

	while(!Q.empty()){

		for(int i = 0; i < Group_G[Q.front()].size(); i++){

			int child = Group_G[Q.front()][i];
			if(child == PARENT[0][Q.front()])continue;

			num_UP[Q.front()] += num_UP[child];
			num_DOWN[Q.front()] += num_DOWN[child];
		}

		if(PARENT[0][Q.front()] != -1){

			num_out[PARENT[0][Q.front()]]--;
			if(num_out[PARENT[0][Q.front()]] == 0){

				Q.push(PARENT[0][Q.front()]);
			}
		}

		Q.pop();
	}

	//移動の向きを確認
	for(int i = 0; i < num_bridge; i++){

		int FROM = getGroupIndex(find(bridge[i].a));
		int TO = getGroupIndex(find(bridge[i].b));

		if(DEPTH[TO] > DEPTH[FROM]){
			swap(FROM,TO);
		}

		if(num_UP[FROM] > 0 && num_DOWN[FROM] > 0){

			printf("No\n");
			return 0;
		}

		if(num_UP[FROM] > 0){

			if(FROM == getGroupIndex(find(bridge[i].a))){

				ANS.push_back(Edge2(bridge[i].a,bridge[i].b));

			}else{

				ANS.push_back(Edge2(bridge[i].b,bridge[i].a));
			}

		}else{ //num_DOWN[FROM] > 0

			if(FROM == getGroupIndex(find(bridge[i].a))){

				ANS.push_back(Edge2(bridge[i].b,bridge[i].a));

			}else{

				ANS.push_back(Edge2(bridge[i].a,bridge[i].b));
			}
		}
	}

	//二重辺連結成分内に辺を張る
	for(int i = 0; i < N; i++){

		check[i] = false;
	}

	for(int i = 0; i < E; i++){
		if(is_bridge[edge[i].index])continue;
		if(check[edge[i].s])continue;

		makeEdge(edge[i].s,-1);
	}

	printf("Yes\n");

	for(int i = 0; i < ANS.size(); i++){

		printf("%d %d\n",ANS[i].from+1,ANS[i].to+1);
	}

	return 0;
}