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.math.*;

public class Main { 
    
    public static void main(String[] args) throws java.lang.Exception { 
        Reader pm =new Reader(); 
        //Scanner pm = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int t = 1;
        while(t-- > 0){
            int n = pm.nextInt();
            TreeSet<Integer> ts1 = new TreeSet<>(Collections.reverseOrder());
            TreeSet<Integer> ts2 = new TreeSet<>();
            int[] a = new int[n];
            int[] b = new int[n];
            HashMap<Integer, Integer> hm = new HashMap<>();
            HashMap<Integer, Integer> hm2 = new HashMap<>();
            for(int i=0;i<n;i++) {
                a[i] = pm.nextInt();
                b[i] = pm.nextInt();
                if(a[i] > b[i]) {
                    ts2.add(b[i]);
                } else 
                    ts1.add(a[i]);
                hm.put(a[i], i+1);
                hm2.put(b[i], i+1);
            }
            //System.out.println(ts1+" "+ts2);
            HashMap<Integer, Integer> inx = new HashMap<>();
            int cnt = 0;
            for(int i:ts1) {
                inx.put(i, ++cnt);
            }
            HashMap<Integer, Integer> inx2 = new HashMap<>();
            cnt = 0;
            for(int i:ts2) {
                inx2.put(i, ++cnt);
            }
            // int ans = Integer.MIN_VALUE;
            // int ind = 0;
            // for(int i=0;i<n;i++) {
            //     int pl = 0;
            //     int id = -1;
            //     if(a[i] < b[i]) {
            //         if(ts1.floor(b[i]) == null) {
            //             pl = 0;
            //             id = i;
            //         } else {
            //             int lo = ts1.floor(b[i]);
            //             int dd = inx.get(lo);
            //             pl = dd;
            //             if(inx.get(a[i]) <= dd)
            //                 pl--;
            //             id = i;
            //         }
            //        // System.out.println(a[i]+" "+b[i]+" "+ts1.floor(b[i]));
            //     } else {
            //          if(ts2.ceiling(b[i]) == null) {
            //             pl = 0;
            //             id = i;
            //         } else {
            //             int lo = ts2.ceiling(b[i]);
            //             int dd = inx2.get(lo);
            //             pl = ts2.size() - dd + 1;
            //             if(inx2.get(a[i]) >= dd)
            //                 pl--;
            //             id = i;
            //         }
            //        // System.out.println(a[i]+" "+b[i]+" "+ts2.ceiling(b[i]));
            //     }
            //     //System.out.println(pl+1);
            //     if(ans < pl+1) {
            //         ans = pl+1;
            //         ind = id;
            //     }
            // }
            //System.out.println(ind);

            ArrayList<Integer> al = new ArrayList<>();

            for(int i: ts1) {
                int ind2 = hm.get(i);
                al.add(ind2);

            }
            ArrayList<Integer> al2 = new ArrayList<>();

            for(int i: ts2) {
                int ind2  = hm2.get(i);
                al2.add(ind2);

            }
            if(al.size() > al2.size()) {
                System.out.println(al.size());
                StringBuffer sb = new StringBuffer();
                for(int i=0;i<al.size();i++) {
                    sb.append(al.get(i)+" ");
                }
                System.out.println(sb);
            } else {
                System.out.println(al2.size());
                StringBuffer sb = new StringBuffer();
                for(int i=0;i<al2.size();i++) {
                    sb.append(al2.get(i)+" ");
                }
                System.out.println(sb);
            }
            // for(int i=0;i<n;i++) {
            //     if(i == ind) {
            //         if(a[i] < b[i]) {
            //            // al.add(ind+1);
            //             TreeSet<Integer> head = (TreeSet<Integer>)ts1.headSet(b[i]);
            //             for(Integer j:head) 
            //                 al.add(hm.get(j));
            //         } else {
            //             //al.add(ind+1);
            //             TreeSet<Integer> head = (TreeSet<Integer>)ts2.tailSet(b[i]);
            //             for(Integer j:head) 
            //                 al.add(hm.get(j));
            //         }
            //         break;
            //     }
            // }
            // //Collections.sort(al);
            // System.out.println(al.size());
            // StringBuffer sb = new StringBuffer();
            // for(int i=0;i<al.size();i++) {
            //     sb.append(al.get(i)+" ");
            // }
            // System.out.println(sb);
        }
        //end of tests
        
    }
    //end of main class

    static int countInRange(int arr[], int n, int x, int y) { 
        // initialize result 
        int count = 0; 
        count = upperIndex(arr, n, y) -  
                lowerIndex(arr, n, x) + 1; 
        return count; 
    } 
    
    
    static int lowerIndex(int arr[], int n, int x) { 
        int l = 0, h = n - 1; 
        while (l <= h)  
        { 
            int mid = (l + h) / 2; 
            if (arr[mid] >= x) 
                h = mid - 1; 
            else
                l = mid + 1; 
        } 
        return l; 
    } 
      
    // function to find last index <= y 
    static int upperIndex(int arr[], int n, int y) { 
        int l = 0, h = n - 1; 
        while (l <= h)  
        { 
            int mid = (l + h) / 2; 
            if (arr[mid] <= y) 
                l = mid + 1; 
            else
                h = mid - 1; 
        } 
        return h; 
    }
    
    public static StringBuilder dec_to_bin(long n) {
        // decimal to binary upto 30 binaries
        if(n==0) {
            StringBuilder str=new StringBuilder("");
            for(int i=0;i<30;i++) {
                str.append("0");
            }
            return str;
        }
        StringBuilder str=new StringBuilder("");
        while(n!=0) {
            str.append(n%2L);
            n/=2L;
        }
        str=str.reverse();
        StringBuilder tmp_str=new StringBuilder("");
        int len=str.length();
        while(len!=30) {
            tmp_str.append("0");
            len++;
        }
        tmp_str.append(str);
        return tmp_str;
    }
    
    private static int binarySearchPM(int[] arr, int key){
        int n = arr.length;
        int mid = -1;
        int begin = 0,end=n;
        while(begin <= end){
            mid = (begin+end) / 2;
            if(mid == n){
                return n;
            }
            if(key < arr[mid]){
                end = mid-1;
            } else if(key > arr[mid]){
                begin = mid+1;
            } else {
                return mid;
            }
        }
        //System.out.println(begin+" "+end);
        return -begin; //expected Index
    }
    
    static class Reader { 
        final private int BUFFER_SIZE = 1 << 16; 
        private DataInputStream din; 
        private byte[] buffer; 
        private int bufferPointer, bytesRead; 
  
        public Reader() 
        { 
            din = new DataInputStream(System.in); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public Reader(String file_name) throws IOException 
        { 
            din = new DataInputStream(new FileInputStream(file_name)); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public String readLine() throws IOException 
        { 
            byte[] buf = new byte[64]; // line length 
            int cnt = 0, c; 
            while ((c = read()) != -1) 
            { 
                if (c == '\n') 
                    break; 
                buf[cnt++] = (byte) c; 
            } 
            return new String(buf, 0, cnt); 
        } 
  
        public int nextInt() throws IOException 
        { 
            int ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do
            { 
                ret = ret * 10 + c - '0'; 
            }  while ((c = read()) >= '0' && c <= '9'); 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public long nextLong() throws IOException 
        { 
            long ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public double nextDouble() throws IOException 
        { 
            double ret = 0, div = 1; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
  
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
  
            if (c == '.') 
            { 
                while ((c = read()) >= '0' && c <= '9') 
                { 
                    ret += (c - '0') / (div *= 10); 
                } 
            } 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        private void fillBuffer() throws IOException 
        { 
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
            if (bytesRead == -1) 
                buffer[0] = -1; 
        } 
  
        private byte read() throws IOException 
        { 
            if (bufferPointer == bytesRead) 
                fillBuffer(); 
            return buffer[bufferPointer++]; 
        } 
  
        public void close() throws IOException 
        { 
            if (din == null) 
                return; 
            din.close(); 
        } 
    }
}