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:

/*
9 2
        1 1 1 1 1 0 0 0 0
        1 2
        1 5
        5 6
        5 7
        2 3
        2 4
        3 8
        3 9
*/




import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Question{


    static LinkedList<Integer> adj[] ;
    static boolean[] visited;
    static boolean[] visited_;
    static int[] ans;
    static int count_ = 0;
    public static  void main(String[] args) throws IOException {
        Reader.init(System.in);
        int n = Reader.nextInt();
        int[][] arr = new int[n][3];
        for (int i = 0 ; i < n ; i++){
            arr[i][0] = Reader.nextInt();
            arr[i][1] = Reader.nextInt();
            arr[i][2] = i;

        }
        LinkedList<LinkedList<Integer>> list1 = new LinkedList<>();
        LinkedList<LinkedList<Integer>> list2 = new LinkedList<>();
        //ArrayList<ArrayList<Integer>> list2 = new ArrayList<>();
        sortbyColumn(arr,0);
        for (int i = 0 ; i< n ; i++){
            LinkedList<Integer> l = new LinkedList<>();
            l.add(arr[i][0]);
            l.add(arr[i][1]);
            l.add(arr[i][2]);
            if (arr[i][0]>arr[i][1]){
                list1.add(l);
            }
            else{
                list2.add(l);
            }
        }


        if (list1.size()>list2.size()){
            System.out.println(list1.size());
            while (list1.size()>0){
                LinkedList<Integer> list = list1.remove(0);
                System.out.print(list.get(2)+1 + " ");
            }
        }
        else{
            System.out.println(list2.size());
            while (list2.size()>0){
                LinkedList<Integer> list = list2.remove(list2.size()-1);
                System.out.print(list.get(2) + 1 + " ");
            }
        }





    }

    static int countGreater(long arr[], int n, long k)
    {
        int l = 0;
        int r = n - 1;

        // Stores the index of the left most element
        // from the array which is greater than k
        int leftGreater = n;

        // Finds number of elements greater than k
        while (l <= r) {
            int m = l + (r - l) / 2;

            // If mid element is greater than
            // k update leftGreater and r
            if (arr[m] > k) {
                leftGreater = m;
                r = m - 1;
            }

            // If mid element is less than
            // or equal to k update l
            else
                l = m + 1;
        }

        // Return the count of elements greater than k
        return (n - leftGreater);
    }

    static void sortbyColumn(int arr[][], int col)
    {
        // Using built-in sort function Arrays.sort
        Arrays.sort(arr, new Comparator<int[]>() {

            @Override
            // Compare values according to columns
            public int compare(final int[] entry1,
                               final int[] entry2) {

                // To sort in descending order revert
                // the '>' Operator
                if (entry1[col] > entry2[col])
                    return 1;
                else
                    return -1;
            }
        });  // End of function call sort().
    }
    static int binarySearchCount(long arr[], int n, long key,int left)
    {
        int right = n;

        int mid = 0;
        while (left < right) {
            mid = (right + left) >> 1;

            // Check if key is present in array
            if (arr[mid] == key) {

                // If duplicates are present it returns
                // the position of last element
                while (mid+1<n && arr[mid + 1] == key)
                    mid++;
                break;
            }

            // If key is smaller, ignore right half
            else if (arr[mid] > key)
                right = mid;

                // If key is greater, ignore left half
            else
                left = mid + 1;
        }

        // If key is not found in array then it will be
        // before mid
        while (mid > - 1 && arr[mid] > key)
            mid--;

        // Return mid + 1 because of 0-based indexing
        // of array
        return mid + 1;
    }

    static long gcd(long a, long b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);

    }

    // method to return LCM of two numbers
    static long lcm(long a, long b)
    {
        return (a*b)/gcd(a, b);
    }

    static long fun(long n){
        long max = -1;
        for (int i = 0 ; i < n ; i++){
            String x = Integer.toString(i);
            long product = 1;
            for (int j = 0 ; j < x.length() ; j++){
                product = product * Long.parseLong(Character.toString(x.charAt(j)));
            }
            max = Math.max(product,max);
        }
        return max;
    }

    public static void print2D(int mat[][])
    {
        // Loop through all rows
        for (int[] row : mat)

            // converting each row as string
            // and then printing in a separate line
            System.out.println(Arrays.toString(row));
    }




}



class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}

class MergeSort {
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    void merge(int arr[], int l, int m, int r) {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        int L[] = new int[n1];
        int R[] = new int[n2];

        /*Copy data to temp arrays*/
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];


        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
    void sort(int arr[], int l, int r) {
        if (l < r) {
            // Find the middle point
            int m = (l + r) / 2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr, m + 1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    static long phi(long n,long R)
    {

        long result = R;


        for (long p = 2; p * p <= n; ++p)
        {


            if (n % p == 0)
            {


                while (n % p == 0)
                    n =n/p;
                result =result - ( result / p);
            }
        }


        //System.out.println("n" + n);
        if (n > 1)
            result -= result / n;
        return result;
    }
}

class person{
    int index;
    int money;

    public person(int index, int money) {
        this.index = index;
        this.money = money;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    public void setMoney(int money) {
        this.money = money;
    }

    public int getIndex() {
        return index;
    }

    public int getMoney() {
        return money;
    }
}

class StudentComparator implements Comparator<person>{

    // Overriding compare()method of Comparator
    // for descending order of cgpa
    public int compare(person s1, person s2) {
        if (s1.money > s2.money)
            return 1;
        else if (s1.money < s2.money) {
            return -1;
        }
        else{
            if (s1.index >s2.index){
                return 1;
            }
            else{
                return -1;
            }
        }

    }
}