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.*; 
import java.math.BigInteger;
import java.util.*;
  
public class Main {
	public static int[] nums;
	public static int[] indices;
	public static int moveNum;
	public static int[][] moves;
    public static void main(String[] args) throws IOException {
        FastScanner sc=new FastScanner();
        int N = sc.nextInt();
        int[][] pairs = new int[N][2];
        for (int i = 0; i < N; i++) {
        	for (int j = 0; j < 2; j++) {
        		pairs[i][j] = sc.nextInt();
        	}
        }
        int[] indices1 = method1(pairs);
        int[] indices2 = method2(pairs);
        if (indices1.length >= indices2.length) {
        	System.out.println(indices1.length);
        	for (int i = 0; i < indices1.length; i++) {
        		System.out.print(indices1[i] + " ");
        	}
        } else {
        	System.out.println(indices2.length);
        	for (int i = 0; i < indices2.length; i++) {
        		System.out.print(indices2[i] + " ");
        	}
        }
    }
    
    public static int[] method1(int[][] pairs) {
    	int[][] valid = new int[pairs.length][3];
    	int V = 0;
    	for (int i = 0; i < pairs.length; i++) {
    		if (pairs[i][0] < pairs[i][1]) {
    			valid[i][0] = pairs[i][0];
    			valid[i][1] = pairs[i][1];
    			valid[i][2] = i+1;
    			V++;
    		} else {
    			//Invalid
    			valid[i][1] = 0;
    		}
    	}
    	
    	Arrays.sort(valid, new Comparator<int[]>() {
    		  @Override
    		  public int compare(int[] arr1, int[] arr2) {
    		    return arr2[1]-arr1[1];
    		  }
    	});
    	int[] indices = new int[V];
    	for (int i = 0; i < V; i++) {
    		indices[i] = valid[i][2];
    	}
    	return indices;
    }
    
    public static int[] method2(int[][] pairs) {
    	int[][] valid = new int[pairs.length][3];
    	int V = 0;
    	for (int i = 0; i < pairs.length; i++) {
    		if (pairs[i][0] > pairs[i][1]) {
    			valid[i][0] = pairs[i][0];
    			valid[i][1] = pairs[i][1];
    			valid[i][2] = i+1;
    			V++;
    		} else {
    			//Invalid
    			valid[i][0] = Integer.MAX_VALUE;
    		}
    	}
    	
    	Arrays.sort(valid, new Comparator<int[]>() {
    		  @Override
    		  public int compare(int[] arr1, int[] arr2) {
    		    return arr1[0]-arr2[0];
    		  }
    	});
    	int[] indices = new int[V];
    	for (int i = 0; i < V; i++) {
    		indices[i] = valid[i][2];
    	}
    	return indices;
    }
    
    static class FastScanner
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastScanner() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
}