Note that girls in Arpa’s land are really attractive.

Arpa loves overnight parties. In the middle of one of these parties Mehrdad suddenly appeared. He saw n pairs of friends sitting around a table. i-th pair consisted of a boy, sitting on the ai-th chair, and his girlfriend, sitting on the bi-th chair. The chairs were numbered 1 through 2n in clockwise direction. There was exactly one person sitting on each chair.

<image>

There were two types of food: Kooft and Zahre-mar. Now Mehrdad wonders, was there any way to serve food for the guests such that: 

  * Each person had exactly one type of food, 
  * No boy had the same type of food as his girlfriend, 
  * Among any three guests sitting on consecutive chairs, there was two of them who had different type of food. Note that chairs 2n and 1 are considered consecutive. 



Find the answer for the Mehrdad question. If it was possible, find some arrangement of food types that satisfies the conditions.

Input

The first line contains an integer n (1 ≤ n ≤ 105) — the number of pairs of guests.

The i-th of the next n lines contains a pair of integers ai and bi (1 ≤ ai, bi ≤ 2n) — the number of chair on which the boy in the i-th pair was sitting and the number of chair on which his girlfriend was sitting. It's guaranteed that there was exactly one person sitting on each chair. 

Output

If there is no solution, print -1.

Otherwise print n lines, the i-th of them should contain two integers which represent the type of food for the i-th pair. The first integer in the line is the type of food the boy had, and the second integer is the type of food the girl had. If someone had Kooft, print 1, otherwise print 2.

If there are multiple solutions, print any of them.

Example

Input

3
1 4
2 5
3 6


Output

1 2
2 1
1 2
import java.util.*;
import java.io.*;

public class ggg {

	private static InputStream stream;
	private static byte[] buf = new byte[1024];
	private static int curChar;
	private static int numChars;
	private static SpaceCharFilter filter;
	private static PrintWriter pw;

	private static void soln(){
		int n=nextInt();
		LinkedList<Integer>[] graph=new LinkedList[2*n];
		for(int i=0;i<2*n;i++)
			graph[i]=new LinkedList<Integer>();
		int[][] pairs=new int[n][2];
		for(int i=0;i<n;i++){
			int a=nextInt();
			int b=nextInt();
			graph[a-1].add(b-1);
			graph[b-1].add(a-1);
			pairs[i][0]=a-1;
			pairs[i][1]=b-1;
		}
		for(int i=0;i<n;i++){
			int a=2*i;
			int b=2*i+1;
			graph[a].add(b);
			graph[b].add(a);
		}
		int[] colour=DFS(graph,2*n);
		for(int i=0;i<n;i++){
			int a=pairs[i][0];
			int b=pairs[i][1];
			pw.println(colour[a]+" "+colour[b]);
		}
	}
	
	private static int knapsack(int[] val,int[] w, int W,ArrayList<LinkedList<Integer>> l){
		int[][] old=new int[2][W+1];
		int i=0;
		while(i<l.size()){
			int j=0;
			int[][] mat_new=new int[2][W+1];
			for(int k=0;k<W+1;k++){
				mat_new[0][k]=old[0][k];
				mat_new[1][k]=old[1][k];
			}
			int tot_w=0;
			int tot_b=0;
			Iterator<Integer> q=l.get(i).listIterator();
			while(q.hasNext()){
				int a=q.next();
				tot_w+=w[a-1];
				tot_b+=val[a-1];
			}
			//System.out.println(tot_w+" "+tot_b);
			if(i%2!=0){
				while(++j<=W){
					Iterator<Integer> k=l.get(i).listIterator();
					while(k.hasNext()){
						int a=k.next();
						if(w[a-1]<=j){
							mat_new[1][j]=max(val[a-1]+old[0][j-w[a-1]],max(mat_new[1][j],old[0][j]));
						}else{
							mat_new[1][j]=max(old[0][j],mat_new[1][j]);
						}	
					}
					if(tot_w<=j){	
						mat_new[1][j]=max(tot_b+old[0][j-tot_w],max(mat_new[1][j],old[0][j]));
					}else{
						mat_new[1][j]=max(old[0][j],mat_new[1][j]);
					}
				}
			}else{
				while(++j<=W){
					Iterator<Integer> k=l.get(i).listIterator();
					while(k.hasNext()){
						//System.out.println(a);
						int a=k.next();
						//System.out.println(a);
						if(w[a-1]<=j){
							mat_new[0][j]=max(val[a-1]+old[1][j-w[a-1]],max(mat_new[0][j],old[1][j]));
						}else{
							mat_new[0][j]=max(old[1][j],mat_new[0][j]);
						}	
					}
					if(tot_w<=j){
						mat_new[0][j]=max(tot_b+old[1][j-tot_w],max(mat_new[0][j],old[1][j]));
					}else{
						mat_new[0][j]=max(old[1][j],mat_new[0][j]);
					}
				}
				//for(int t=0;t<=W;t++)
					//System.out.println(mat_new[0][t]);
			}
			old=mat_new;
			i++;
		}
		return (l.size()%2 !=0)?old[0][W]:old[1][W];
	}
	private static int DFSUtils(int v,LinkedList<Integer>[] g,int[] colour){
		Iterator<Integer> i=g[v].listIterator();
		while(i.hasNext()){
			int j=i.next();
			if(colour[j]==0){
				if(colour[v]==1)
					colour[j]=2;
				else
					colour[j]=1;
				if(DFSUtils(j,g,colour)==-1)
					return -1;
			}else if(colour[j]==colour[v])
				return -1;
		}
		return 0;
	}
	private static int[] DFS(LinkedList<Integer>[] g,int n){
		int[] colour=new int[2*n];
		for(int i=0;i<n;i++){
			if(colour[i]==0){
				colour[i]=1;
				//System.out.println(1);
				if(DFSUtils(i,g,colour)==-1)
					return null;
			}
		}
		return colour;
	}
	private static long gcd(long a,long b){
		if(b==0)
			return a;
		else return gcd(b,a%b);
	}
	private static long lcm(long a,long b){
		return (a*b)/gcd(a,b);
	}
	private static int min(int a,int b){
		if(a>b)
			return b;
		else
			return a;
	}
	private static class Pair implements Comparable<Pair>{
		int x;
		int y;
		public Pair(int a,int b){
			x=a;
			y=b;
		}
		@Override
		public int compareTo(Pair arg0) {
			if(this.x > arg0.x)
				return 1;
			return 0;
		}
	}
	static long pow(int a, long b, int MOD) {
		long x = 1, y = a;
		    while(b > 0) {
		        if(b%2 == 1) {
		            x=(x*y);
		            if(x>MOD) x%=MOD;
		        }
		        y = (y*y);
		        if(y>MOD) y%=MOD;
		        b /= 2;
		    }
		    return x;
		}
		 
		static long modInverse(int a,long b, int m) {
			//pw.println((m-2)*b);
		    return pow(a,(m-2)*b,m);
		}
	private static void computeLpsArray(String pat,int size,int[] lps){
		int len=0;
		int i=1;
		lps[0]=0;
		while(i<size){
			if(pat.charAt(i)==pat.charAt(len)){
				len++;
				lps[i]=len;
				i++;
			}else{
				if(len!=0){
					len=lps[len-1];
				}else{
					lps[i]=len;
					i++;
				}
			}
		}
	}
	private static int KMP(String pat,String txt){
		int m=pat.length();
		int n=txt.length();
		int[] lps=new int[m];
		int j=0;
		int len=0;
		int index=0;
		computeLpsArray(pat,m,lps);
		int i=0;
		while(i<n){
			if(pat.charAt(j)==txt.charAt(i)){
				i++;
				j++;
			}else{
				if(j!=0)
					j=lps[j-1];
				else
					i++;
			}
			if(len<j){
				len=j;
				//pw.println(i);
				index=i;
			}
		}
		return index-len;
	}
	private static int max(int a,int b){
		if(a>b)
			return a;
		return b;
	}
	public static void main(String[] args) {
		InputReader(System.in);
		pw = new PrintWriter(System.out);
		soln();
		pw.close();
	}

	// To Get Input
	// Some Buffer Methods

	public static void InputReader(InputStream stream1) {
		stream = stream1;
	}

	private static boolean isWhitespace(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private static boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}

	private static int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	private static int nextInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	private static long nextLong() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	private static String nextToken() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	private static String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	private static int[] nextIntArray(int n) {
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = nextInt();
		}
		return arr;
	}

	private static long[] nextLongArray(int n) {
		long[] arr = new long[n];
		for (int i = 0; i < n; i++) {
			arr[i] = nextLong();
		}
		return arr;
	}

	private static void pArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static void pArray(long[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}

	private interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}

}