Problem: Berland consists of n cities and m bidirectional roads connecting pairs of cities. There is no road connecting a city to itself, and between any pair of cities there is no more than one road. It is possible to reach any city from any other moving along roads.

Currently Mr. President is in the city s and his destination is the city t. He plans to move along roads from s to t (s ≠ t).

That's why Ministry of Fools and Roads has difficult days. The minister is afraid that Mr. President could get into a traffic jam or get lost. Who knows what else can happen!

To be sure that everything goes as planned, the minister decided to temporarily make all roads one-way. So each road will be oriented in one of two possible directions. The following conditions must be satisfied:

  * There should be no cycles along roads after orientation. 
  * The city s should be the only such city that all its roads are oriented out (i.e. there are no ingoing roads to the city s and the city s is the only such city). 
  * The city t should be the only such city that all its roads are oriented in (i.e. there are no outgoing roads from the city t and the city t is the only such city). 



Help the minister solve his problem. Write a program to find any such orientation of all roads or report that no solution exists.

Input

Each test in this problem contains one or more test cases to solve. The first line of the input contains positive number T — the number of cases to solve.

Each case starts with a line containing four integers n, m, s and t (2 ≤ n ≤ 4·105, 1 ≤ m ≤ 106, 1 ≤ s, t ≤ n, s ≠ t) — the number of cities, the number of roads and indices of departure and destination cities. The cities are numbered from 1 to n.

The following m lines contain roads, one road per line. Each road is given as two integer numbers xj, yj (1 ≤ xj, yj ≤ n, xj ≠ yj), which means that the j-th road connects cities xj and yj. There is at most one road between any pair of cities. It is possible to reach any city from any other moving along roads.

The sum of values n over all cases in a test doesn't exceed 4·105. The sum of values m over all cases in a test doesn't exceed 106.

Output

For each case print "Yes" if the answer exists. In the following m lines print roads in the required directions. You can print roads in arbitrary order. If there are multiple answers, print any of them.

Print the only line "No" if there is no answer for a case.

Example

Input

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


Output

Yes
1 2
3 2
4 3
1 4
No

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class RoadOrientation {

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;
	boolean eof;

	void writeLabels(Node v) {
		if (v == null) {
			return;
		}
		writeLabels(v.l);
		label[v.id] = ptr++;
		writeLabels(v.r);
	}

	static class Node {
		Node l, r, up;

		int size;
		int id;

		void update() {
			size = 1 + getSize(l) + getSize(r);
		}

		static int getSize(Node v) {
			return v == null ? 0 : v.size;
		}

		void push() {
		}

		boolean isRoot() {
			return up == null;
		}

		public Node(int id) {
			this.id = id;
			update();
		}

		static private void relink(Node v, Node u) {
			Node t = u.up;
			if (v != null) {
				v.up = t;
			}
			if (t != null) {
				if (t.l == u) {
					t.l = v;
				} else if (t.r == u) {
					t.r = v;
				}
			}
		}

		private void rotate() {
			Node u = up;

			if (u.l == this) {
				relink(r, this);
				r = u;
			} else {
				relink(l, this);
				l = u;
			}

			relink(this, u);
			u.up = this;
			u.update();
		}
	}

	static void splay(Node v) {
		if (v.isRoot()) {
			v.push();
			return;
		}
		do {
			Node u = v.up;
			Node t = u.up;
			boolean uRoot = u.isRoot();
			if (!uRoot) {
				t.push();
			}
			u.push();
			v.push();
			if (!uRoot) {
				((t.l == u) == (u.l == v) ? u : v).rotate();
			}
			v.rotate();
		} while (!v.isRoot());
		v.update();
	}

	int[] vs, us;
	List<Integer>[] g;

	int[] par;
	int[] depth;

	int[] order;
	int ptr;

	int[] label;

	void dfs(int v, int p, int curD) {
		order[ptr++] = v;
		par[v] = p;
		depth[v] = curD;

		for (int u : g[v]) {
			if (depth[u] == -1) {
				dfs(u, v, curD + 1);
			}
		}
	}

	int getPos(Node v) {
		splay(v);
		return Node.getSize(v.l);
	}

	boolean[] solve(int n, int m, int s, int t, int[] vs, int[] us) {
		this.vs = vs;
		this.us = us;

		// TODO: remove ArrayLists
		g = new List[n];
		for (int i = 0; i < n; i++) {
			g[i] = new ArrayList<>();
		}
		for (int i = 0; i < m; i++) {
			g[vs[i]].add(us[i]);
			g[us[i]].add(vs[i]);
		}

		par = new int[n];
		depth = new int[n];
		order = new int[n];
		ptr = 0;

		Arrays.fill(depth, -1);

		dfs(s, -1, 0);

		Node[] nodes = new Node[n];

		Node root = null;

		for (int v = t; v != -1; v = par[v]) {
			nodes[v] = new Node(v);
			nodes[v].r = root;
			if (root != null) {
				root.up = nodes[v];
			}
			root = nodes[v];
			root.update();
		}

		for (int v : order) {
			if (nodes[v] == null) {
				return null;
			}
			for (int u : g[v]) {
				if (nodes[u] != null || depth[u] <= depth[v] + 1) {
					continue;
				}

				int end = u;
				while (nodes[end] == null) {
					end = par[end];
				}

				if (end == v) {
					return null;
				}

				int posEnd = getPos(nodes[end]);
				int posV = getPos(nodes[v]);

				if (posV < posEnd) {
					// v is root

					Node nxt = nodes[v].r; // should not be null as v is before
											// end
					nxt.up = null;
					nodes[v].r = null;
					nodes[v].update();

					while (nxt.l != null) {
						nxt = nxt.l;
					}

					splay(nxt);

					Node cur = null;

					while (nodes[u] == null) {
						nodes[u] = new Node(u);
						nodes[u].l = cur;
						if (cur != null) {
							cur.up = nodes[u];
						}
						nodes[u].update();
						cur = nodes[u];
						u = par[u];
					}

					nxt.l = cur;
					cur.up = nxt;
					nxt.update();

					nxt.up = nodes[v];
					nodes[v].r = nxt;
					nodes[v].update();

				} else {

					Node nxt = nodes[v].l;
					nxt.up = null;
					nodes[v].l = null;
					nodes[v].update();

					while (nxt.r != null) {
						nxt = nxt.r;
					}

					splay(nxt);

					Node cur = null;

					while (nodes[u] == null) {
						nodes[u] = new Node(u);
						nodes[u].r = cur;
						if (cur != null) {
							cur.up = nodes[u];
						}
						nodes[u].update();
						cur = nodes[u];
						u = par[u];
					}

					nxt.r = cur;
					cur.up = nxt;
					nxt.update();

					nxt.up = nodes[v];
					nodes[v].l = nxt;
					nodes[v].update();
				}

			}
		}

		splay(nodes[s]);

		ptr = 0;
		label = new int[n];

		writeLabels(nodes[s]);

		boolean[] ret = new boolean[m];
		for (int i = 0; i < m; i++) {
			ret[i] = label[vs[i]] < label[us[i]];
		}

		return ret;
	}

	void checkAnswer(int n, int m, int s, int t, int[] vs, int[] us,
			boolean[] ans) {
		if (ans == null) {
			return;
		}

		boolean[] hasIn = new boolean[n];
		boolean[] hasOut = new boolean[n];

		for (int i = 0; i < m; i++) {
			if (ans[i]) {
				hasOut[vs[i]] = true;
				hasIn[us[i]] = true;
			} else {
				hasOut[us[i]] = true;
				hasIn[vs[i]] = true;
			}
		}

		for (int i = 0; i < n; i++) {
			if (i == s) {
				if (hasIn[i]) {
					throw new AssertionError();
				}
			} else if (i == t) {
				if (hasOut[i]) {
					throw new AssertionError();
				}
			} else if (!hasIn[i] || !hasOut[i]) {
				throw new AssertionError();
			}
		}
	}

	void run() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);

//		for (int i = 0; i < Integer.MAX_VALUE; i++) {
//			randomTest(4, 4);
//		}

		int q = nextInt();
		while (q-- > 0) {

			int n = nextInt();
			int m = nextInt();

			int s = nextInt() - 1;
			int t = nextInt() - 1;

			int[] vs = new int[m];
			int[] us = new int[m];
			for (int i = 0; i < m; i++) {
				vs[i] = nextInt() - 1;
				us[i] = nextInt() - 1;
			}

			boolean[] ans = solve(n, m, s, t, vs, us);
			if (ans == null) {
				out.println("No");
			} else {

				boolean[] hasIn = new boolean[n];
				boolean[] hasOut = new boolean[n];

				for (int i = 0; i < m; i++) {
					if (ans[i]) {
						hasOut[vs[i]] = true;
						hasIn[us[i]] = true;
					} else {
						hasOut[us[i]] = true;
						hasIn[vs[i]] = true;
					}
				}

				for (int i = 0; i < n; i++) {
					if (i == s) {
						if (hasIn[i]) {
							throw new AssertionError();
						}
					} else if (i == t) {
						if (hasOut[i]) {
							throw new AssertionError();
						}
					} else if (!hasIn[i] || !hasOut[i]) {
						throw new AssertionError();
					}
				}

				out.println("Yes");
				for (int i = 0; i < m; i++) {
					if (ans[i]) {
						out.println((vs[i] + 1) + " " + (us[i] + 1));
					} else {
						out.println((us[i] + 1) + " " + (vs[i] + 1));
					}
				}
			}
		}

		out.close();
	}

	Random rng = new Random();

	void randomTest(int n, int m) {
		boolean[][] g = new boolean[n][n];
		for (int i = 0; i < m; i++) {
			int v = -1, u = -1;
			do {
				v = rng.nextInt(n);
				u = rng.nextInt(n);
			} while (v == u || g[v][u]);
			g[v][u] = g[u][v] = true;
		}

		int ptr = 0;
		int[] vs = new int[m];
		int[] us = new int[m];
		for (int i = 0; i < n; i++)
			for (int j = i + 1; j < n; j++) {
				if (g[i][j]) {
					vs[ptr] = i;
					us[ptr] = j;
					ptr++;
				}
			}

		for (int i = 0; i < n; i++) {
			g[i][i] = true;
		}

		for (int k = 0; k < n; k++)
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++) {
					g[i][j] |= g[i][k] && g[k][j];
				}

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				if (!g[i][j]) {
					System.err.println("not-connected");
					return;
				}
			}

		System.err.println(n + " " + Arrays.toString(vs) + " "
				+ Arrays.toString(us));

		boolean[] ans = solve(n, m, 0, 1, vs, us);
		System.err.println(Arrays.toString(ans));
		checkAnswer(n, m, 0, 1, vs, us, ans);
	}

	public static void main(String[] args) throws IOException {

		new RoadOrientation().run();
	}

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				eof = true;
				return null;
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			eof = true;
			return null;
		}
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}