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.util.*;
import java.util.Map.Entry;
import java.io.*;
        public class uu {
        	public static void main(String[] args) throws IOException {
        		Scanner sc =new Scanner(System.in);
        		PrintWriter pw =new PrintWriter(System.out);
        		int n =sc.nextInt();
        		TreeMap<Integer, Integer>tm1 =new TreeMap<Integer, Integer>(),tm2=new TreeMap<Integer, Integer>();
        		for  (int i=0;n-->0;++i) {
        			int a=sc.nextInt(),b=sc.nextInt();
        			if (a>b)
        				tm1.put(b,i+1);
        			else
        				tm2.put(a,i+1);
        		}
        		if (tm1.size()>tm2.size()) {
        			pw.println(tm1.size());
        			while (!tm1.isEmpty())
        				pw.print(tm1.pollFirstEntry().getValue()+" ");
        		}else
        		{
        			pw.println(tm2.size());
        			while (!tm2.isEmpty())
        				pw.print(tm2.pollLastEntry().getValue()+" ");
        		}
         		pw.close();
}
    		static long gcd(long a, long b) 
    		{ 
    		    if (a == 0) 
    		        return b; 
    		    return gcd(b % a, a); 
    		}
			static class Scanner {
				StringTokenizer stringTokenizer;
				BufferedReader bfBufferedReader;
				public Scanner(InputStream system) {
					bfBufferedReader=new BufferedReader(new InputStreamReader( system));
				}
				 public Scanner(String file) throws Exception {
			            bfBufferedReader = new BufferedReader(new FileReader( file));
			        }			 
			        public String next() throws IOException {
			            while (stringTokenizer == null || !stringTokenizer.hasMoreTokens())
			                stringTokenizer = new StringTokenizer( bfBufferedReader.readLine());
			            return stringTokenizer.nextToken();
			        }
			 
			        public String nextLine() throws IOException {
			            return bfBufferedReader.readLine();
			        }
			 
			        public int nextInt() throws IOException {
			            return Integer.parseInt(next());
			        }
			 
			        public double nextDouble() throws IOException {
			            return Double.parseDouble(next());
			        }
			 
			        public char nextChar() throws IOException {
			            return next().charAt(0);
			        }
			 
			        public Long nextLong() throws IOException {
			            return Long.parseLong(next());
			        }
			 
			        public boolean ready() throws IOException {
			            return bfBufferedReader.ready();
			        }
			 
			        public void waitForInput() throws InterruptedException {
			            Thread.sleep(3000);
			        }
			    }
			static class SegmentTree {
			    public static class STNode {
			        int leftIndex;
			        int rightIndex;
			        int sum;
			        STNode leftNode;
			        STNode rightNode;
			    }

			    static STNode constructSegmentTree(int[] A, int l, int r) {
			        if (l == r) {
			            STNode node = new STNode();
			            node.leftIndex = l;
			            node.rightIndex = r;
			            node.sum = A[l];
			            return node;
			        }
			        int mid = (l + r) / 2;
			        STNode leftNode = constructSegmentTree(A, l, mid);
			        STNode rightNode = constructSegmentTree(A, mid+1, r);
			        STNode root = new STNode();
			        root.leftIndex = leftNode.leftIndex;
			        root.rightIndex = rightNode.rightIndex;
			        root.sum = leftNode.sum + rightNode.sum;
			        root.leftNode = leftNode;
			        root.rightNode = rightNode;
			        return root;
			    }

			    static int getSum(STNode root, int l, int r) {
			        if (root.leftIndex >= l && root.rightIndex <= r) {
			            return root.sum;
			        }
			        if (root.rightIndex < l || root.leftIndex > r) {
			            return 0;
			        }
			        return getSum(root.leftNode, l, r) + getSum(root.rightNode, l, r);
			    }

			    /**
			     * 
			     * @param root
			     * @param index index of number to be updated in original array 
			     * @param newValue
			     * @return difference between new and old values
			     */
			    static int updateValueAtIndex(STNode root, int index, int newValue) {
			        int diff = 0;
			        if(root.leftIndex==root.rightIndex && index == root.leftIndex) {
			            // We actually reached to the leaf node to be updated
			            diff = newValue-root.sum;
			            root.sum=newValue;
			            return diff;
			        }
			        int mid = (root.leftIndex + root.rightIndex) / 2;
			        if (index <= mid) {
			            diff= updateValueAtIndex(root.leftNode, index, newValue);
			        } else {
			            diff= updateValueAtIndex(root.rightNode, index, newValue);
			        }
			        root.sum+=diff;
			        return diff;
			    }
			}
        }