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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class d {
    static BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
       StringBuilder sb=new StringBuilder();
        String[] s1=s();
      int n=i(s1[0]);
      Student12[] st=new Student12[n];
      for(int i=0;i<n;i++){
          String[] s2=s();
          int a=i(s2[0]);int b=i(s2[1]);
          st[i]=new Student12(a,b,i);
      }Arrays.sort(st,new Sortbyroll12());
      StringBuilder ans1=new StringBuilder();int countans1=0;
        StringBuilder ans2=new StringBuilder();int countans2=0;
        for(int i=0;i<n;i++){
          if(st[i].r>st[i].l){
              countans1++;ans1.append((st[i].ind+1)+" ");
          }
      }
      Arrays.sort(st,new Sortbyroll123());
      for(int i=0;i<n;i++){
          if(st[i].r<st[i].l){
              countans2++;ans2.append((st[i].ind+1)+" ");
          }
      }if(countans1>countans2){
            System.out.println(countans1);
            System.out.println(ans1.toString());
        }else{
            System.out.println(countans2);
            System.out.println(ans2.toString());
        }
    }static long val=0;
    static long dfs(ArrayList<Integer>[] adj,int[] vis,int first,int second,int i,StringBuilder sb,long[][] colors,long x){
        vis[i]=1;int color=0;
       // System.out.println(i);
        if(adj[i].size()==3) return -1;
        if(first+second==1){
            val+=colors[2][i-1];color=2;vis[i]=color+1;

        }else if(first+second==2){
            val+=colors[1][i-1];color=1;vis[i]=color+1;

        }else
        { val+=colors[0][i-1];sb.append(1+" ");color=0;vis[i]=color+1;}
        //System.out.println(color+" "+i);
        for(Integer J:adj[i]){
            if(vis[J]==0){
                dfs(adj,vis,second,color,J,sb,colors,val);
            }
        }return 0;
    }
    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
    static String[] s() throws IOException {
        return s.readLine().trim().split("\\s+");
    }
    static int i(String ss) {
        return Integer.parseInt(ss);
    }
    static long l(String ss) {
        return Long.parseLong(ss);
    }
    static int MAXN;
    static int[] spf;
    static void sieve() {
        spf[1] = 1;
        for (int i=2; i<MAXN; i++)
            spf[i] = i;
        for (int i=4; i<MAXN; i+=2)
            spf[i] = 2;
        for (int i=3; i*i<MAXN; i++)
        {
            if (spf[i] == i)
            {
                for (int j=i*i; j<MAXN; j+=i)

                    if (spf[j]==j)
                        spf[j] = i;
            }
        }
    }
    static long powerwithmod(long  x, long y, long p) {
        long  res = 1;
        x = x % p;
        while (y > 0) {
            if ((y & 1) == 1)
                res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }static long[] fac ;
    static void calculatefac(long mod){
        fac[0]=1;
        for (int i = 1 ;i <= MAXN; i++)
            fac[i] = fac[i-1] * i % mod;
    }
    static long nCrModPFermat(int n, int r, long mod) {
        if (r == 0)
            return 1;
        fac[0] = 1;
        return (fac[n]*
                modInverse(fac[r], mod)
                % mod * modInverse(fac[n-r], mod)
                % mod) % mod;
    }static long modInverse(long a, long m)
    {
        return (powerwithmod(a, m - 2, m));
    }





}

class Student12 {
    int  l;long r;int ind;
    public Student12(int l, long r,int ind) {
        this.l = l;this.ind=ind;
        this.r = r;
    }

    public String toString()
    {
        return this.l+" ";
    }
}
class Sortbyroll12 implements Comparator<Student12> {

    public int compare(Student12 a, Student12 b){
        if(a.r>=b.r) return -1;
     /*   else if(a.r==b.r){
            if(a.r==b.r){
                return 0;
            }
            if(a.r<b.r) return -1;
            return 1;}*/
        return 1;  }
}
class Sortbyroll123 implements Comparator<Student12> {

    public int compare(Student12 a, Student12 b){
        if(a.r<=b.r) return -1;
     /*   else if(a.r==b.r){
            if(a.r==b.r){
                return 0;
            }
            if(a.r<b.r) return -1;
            return 1;}*/
        return 1;  }
}