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.util.*;
import java.lang.*;
import java.awt.*;
import java.awt.geom.*;
import java.math.*;
import java.text.*;
import java.math.BigInteger.*;
import java.util.Arrays; 

public class   CFGLOBAL3
{
  BufferedReader in;
  StringTokenizer as;
  int nums[][],nums2[][];
  int[] nums1[];
  int a;
  boolean con = true;
 
  ArrayList < Integer >  ar = new ArrayList < Integer >();
    ArrayList < Integer >  ar2 = new ArrayList < Integer >();
      ArrayList < Integer >  ar3 = new ArrayList < Integer >();
          ArrayList < Integer >  ar4 = new ArrayList < Integer >();
  public static void main (String[] args)
  {
    new CFGLOBAL3  ();
  }
  
  public int GCD(int a, int b) {
    if (b==0) return a;
    return GCD(b,a%b);
  }
  
  public int LIS(int arr[])
  {
    int n = arr.length;
    int sun[] = new int [n];
    int cur = 0;
    for(int x = 0;x<n;x++)
    {
      int temp = Arrays.binarySearch(sun,0,cur,arr[x]);
      if(temp < 0)
        temp = -temp -1;
      sun[temp] = arr[x];
      if(temp == cur)
        cur++;
    }
    return cur;
    
  }
  public CFGLOBAL3  ()
  {
    try
    {
      
      in = new BufferedReader (new InputStreamReader (System.in));
       a = nextInt();
       for(int x = 0;x<a;x++)
       {
         int b = nextInt();
         int c = nextInt();
         if( b > c)
         {
           ar.add(b);
           ar.add(c);
           ar.add(x);
         }
         else
         {
           ar2.add(b);
           ar2.add(c);
           ar2.add(x);
         }
       }
       nums = new int [ar.size()/3][3];
       nums2 = new int [ar2.size()/3][3];
       for(int x = 0;x<ar.size();x+=3)
       {
         nums[x/3][0] = ar.get(x);
         nums[x/3][1] = ar.get(x+1);
           nums[x/3][2] = ar.get(x+2);
       }
       for(int x = 0;x<ar2.size();x+=3)
       {
         nums2[x/3][0] = ar2.get(x);
         nums2[x/3][1] = ar2.get(x+1);
                  nums2[x/3][2] = ar2.get(x+2);
       }
       Arrays.sort(nums, (aa,bb) -> Integer.compare(aa[1],bb[1]));
       Arrays.sort(nums2, (aa,bb) -> Integer.compare(aa[1],bb[1]));
 //     for(int x = 0;x<nums2.length;x++)
    //     System.out.println(nums2[x][0] + " " + nums2[x][1] + " " + nums2[x][2]);
       int last = -1;
       int pointer = 0;
       while(pointer < nums.length)
       {
         if(nums[pointer][0] > last)
         {
           ar3.add(nums[pointer][2]);
           last = nums[pointer][1];
         }
         pointer++;
       }
        last = 1000000000;
        pointer = nums2.length-1;
       while(pointer >= 0)
       {
         if(nums2[pointer][0] < last)
         {
           ar4.add(nums2[pointer][2]);
           last = nums2[pointer][1];
         }
         pointer--;
       }
       System.out.println(Math.max(ar4.size(),ar3.size()));
       if(ar4.size() > ar3.size())
       {
         for(int x = 0;x<ar4.size();x++)
         {
           System.out.print((ar4.get(x)+1) + " " );
         }
       }
       else
       {
         for(int x = 0;x<ar3.size();x++)
           System.out.print((ar3.get(x)+1) + " " );
       }
       


    }
    catch(IOException e)
    {

    }
  }
  
  
  
  
  
  
  
  String next () throws IOException
  {
    while (as == null || !as.hasMoreTokens ())
    {
      as = new StringTokenizer (in.readLine ().trim ());
    }
    
    
    return as.nextToken ();
  }
  
  
  
  long nextLong () throws IOException
  {
    return Long.parseLong (next ());
  }
  
  
  int nextInt () throws IOException
  {
    return Integer.parseInt (next ());
  }
  
  
  double nextDouble () throws IOException
  {
    return Double.parseDouble (next ());
  }
  
  
  String nextLine () throws IOException
  {
    return in.readLine ().trim ();
  }
}