Problem: You are given n pairs of integers (a_1, b_1), (a_2, b_2), …, (a_n, b_n). All of the integers in the pairs are distinct and are in the range from 1 to 2 ⋅ n inclusive.

Let's call a sequence of integers x_1, x_2, …, x_{2k} good if either 

  * x_1 < x_2 > x_3 < … < x_{2k-2} > x_{2k-1} < x_{2k}, or 
  * x_1 > x_2 < x_3 > … > x_{2k-2} < x_{2k-1} > x_{2k}. 



You need to choose a subset of distinct indices i_1, i_2, …, i_t and their order in a way that if you write down all numbers from the pairs in a single sequence (the sequence would be a_{i_1}, b_{i_1}, a_{i_2}, b_{i_2}, …, a_{i_t}, b_{i_t}), this sequence is good.

What is the largest subset of indices you can choose? You also need to construct the corresponding index sequence i_1, i_2, …, i_t.

Input

The first line contains single integer n (2 ≤ n ≤ 3 ⋅ 10^5) — the number of pairs.

Each of the next n lines contain two numbers — a_i and b_i (1 ≤ a_i, b_i ≤ 2 ⋅ n) — the elements of the pairs.

It is guaranteed that all integers in the pairs are distinct, that is, every integer from 1 to 2 ⋅ n is mentioned exactly once.

Output

In the first line print a single integer t — the number of pairs in the answer.

Then print t distinct integers i_1, i_2, …, i_t — the indexes of pairs in the corresponding order.

Examples

Input


5
1 7
6 4
2 10
9 8
3 5


Output


3
1 5 3


Input


3
5 4
3 2
6 1


Output


3
3 2 1

Note

The final sequence in the first example is 1 < 7 > 3 < 5 > 2 < 10.

The final sequence in the second example is 6 > 1 < 3 > 2 < 5 > 4.

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.InputMismatchException;
public class DGlobalRound3 {

	public static void main(String[] args) {
		FastScanner in = new FastScanner(System.in);
		int N = in.nextInt();
		Pair[] pears = new Pair[N];
		Pair[] pears2 = new Pair[N];
		for(int i = 0; i < N; i++) {
			int x = in.nextInt();
			int y = in.nextInt();
			
			pears[i] = new Pair(x, y);
			pears2[i] = new Pair(x, y);
		}
		
		HashMap<Pair, Integer> getIndex = new HashMap<>();
		
		int index = 0;
		for(Pair p : pears) {
			getIndex.put(p, index++);
		}
		
		Arrays.sort(pears2);
		
		ArrayList<Integer> list = check(pears, pears2, getIndex);
		
		StringBuilder sb = new StringBuilder();
		
		sb.append(list.size());
		sb.append('\n');
		
		for(int i : list)
			sb.append((i+1) + " ");
		
		System.out.println(sb.toString().trim());
	}
	
	public static ArrayList<Integer> check(Pair[] pears, Pair[] pear2, HashMap<Pair, Integer> getIndex) {
		ArrayList<Pair> ascending = new ArrayList<>();
		ArrayList<Pair> descending = new ArrayList<>();
		for(Pair p : pears) {
			if(p.a < p.b) {
				ascending.add(p);
			}
			else if(p.a > p.b) {
				descending.add(p);
			}
		}
		
		Collections.sort(ascending);
		Collections.sort(descending);
		
		ArrayList<Integer> up = new ArrayList<>();
		ArrayList<Integer> down = new ArrayList<>();
		
		for(int i = ascending.size()-1; i >= 0; i--) {
			up.add(getIndex.get(ascending.get(i)));
		}
		
		for(int i = 0; i < descending.size(); i++) {
			down.add(getIndex.get(descending.get(i)));
		}
		
		return (up.size() >= down.size()) ? up : down;
	}
	
	
	static class Pair implements Comparable<Pair> {
		int a, b;
		public Pair(int x, int y) {
			a = x; b = y;
		}
		
		public int compareTo(Pair other) {
			if(a != other.a) {
				return a - other.a;
			}
			
			return b - other.b;
		}
		
		public boolean equals(Object o) {
			if(!(o instanceof Pair))
				return false;
			Pair p2 = (Pair) o;
			return a == p2.a && b == p2.b;
		}
		
		public String toString() {
			return "(" + a + ", " + b + ")";
		}
	}
	
	/**
	 * Source: Matt Fontaine
	 */
	static class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int chars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
		}

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

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

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

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

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

		public String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}

}
/*
5
1 7
6 4
2 10
9 8
3 5
outputCopy
3
1 5 3
inputCopy
3
5 4
3 2
6 1
outputCopy
3
3 2 1
*/