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

public class CP {
    public static void main(String[] args) throws Exception {
        /*new Thread(null, new Runnable() {
            @Override
            public void run() {
                try {
                    new Solver().solve();
                } catch (Exception e) {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }, "Solver", 1l << 30).start();*/

        new Solver().solve();
    }
}

class Solver {
    IO io = new IO(System.in, System.out);

    int N;
    ArrayList<int[]> inc, dec;

    void solve() throws Exception {
        int i, j, k;
        inc = new ArrayList<>();
        dec = new ArrayList<>();

        N = io.nextInt();
        for (i = 0; i < N; ++i) {
            int a = io.nextInt(), b = io.nextInt();

            if (a < b) inc.add(new int[] {a, b, i + 1});
            else if (a > b) dec.add(new int[] {b, a, i + 1});
        }
        Collections.sort(inc, (int[] a, int[] b) -> a[0] == a[1] ?
                Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
        Collections.sort(dec, (int[] a, int[] b) -> a[0] == a[1] ?
                Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));

        ArrayList<int[]> ans1 = calculate(inc);
        ArrayList<int[]> ans2 = calculate(dec);
        Collections.reverse(ans2);

        if (ans1.size() > ans2.size()) {
            io.println(ans1.size());
            for (int[] itr : ans1) io.printsp(itr[2]);
            io.println();
        } else {
            io.println(ans2.size());
            for (int[] itr : ans2) io.printsp(itr[2]);
            io.println();
        }

        io.flush();
    }

    ArrayList<int[]> calculate(ArrayList<int[]> ar) {
        ArrayList<int[]> ret = new ArrayList<>();
        int allowed = Integer.MAX_VALUE;

        SegmentTree seg = new SegmentTree(ar);

        //for (int[] itr : ar) System.out.print(Arrays.toString(itr));
        //System.out.println();

        while (true) {
            int ind = bs(ar, allowed);

            ind = seg.query(0, ind);
            if (ind < 0) return ret;

            seg.update(ind, -7);
            ret.add(ar.get(ind));
            allowed = ar.get(ind)[1];

            //System.out.println(ind);
        }
    }

    int bs(ArrayList<int[]> ar, int key) {
        if (ar.isEmpty()) return -7;

        int l = 0, r = ar.size() - 1;
        while (true) {
            int mid = l + r >> 1;

            if (l + 1 >= r) {
                if (ar.get(r)[0] < key) return r;
                else if (ar.get(l)[0] >= key) return -7;
                else return l;
            } else if (ar.get(mid)[0] < key) l = mid;
            else r = mid - 1;
        }
    }
}

class SegmentTree {
    int[] A, tree;
    int N;

    SegmentTree(ArrayList<int[]> ar) {
        N = 1; while (N < ar.size()) N <<= 1;
        tree = new int[N * 2 - 1]; Arrays.fill(tree, -7);
        A = new int[ar.size()];
        for (int i = 0; i < ar.size(); ++i) {
            A[i] = ar.get(i)[1];
            tree[i + N - 1] = i;
        }

        for (int i = N - 2; i >= 0; --i) {
            build(i);
        }
    }

    void build(int i) {
        int c1 = i * 2 + 1, c2 = i * 2 + 2;
        if (tree[c1] < 0) tree[i] = tree[c2];
        else if (tree[c2] < 0) tree[i] = tree[c1];
        else if (A[tree[c1]] >= A[tree[c2]]) tree[i] = tree[c1];
        else tree[i] = tree[c2];
    }

    void update(int ind, int val) {
        A[ind] = -7; ind += N - 1;
        tree[ind] = -7; ind = ind - 1 >> 1;
        while (ind >= 0) {
            build(ind);
            ind = ind - 1 >> 1;
        }
    }

    int query(int l, int r) {
        /*int ret = -7, max = -7;
        for ( ; l <= r; ++l) {
            if (A[l] > max) {
                max = A[l];
                ret = l;
            }
        }
        return ret;*/

        return query(0, 0, N - 1, l, r);
    }

    int query(int i, int l, int r, int ql, int qr) {
        int mid = l + r >> 1, i2 = i << 1;

        if (l > qr || r < ql) {
            return -7;
        } else if (l >= ql && r <= qr) {
            return tree[i];
        } else {
            int a = query(i2 + 1, l, mid, ql, qr);
            int b = query(i2 + 2, mid + 1, r, ql, qr);
            if (a < 0) return b;
            else if (b < 0) return a;
            else if (A[a] >= A[b]) return a;
            else return b;
        }
    }
}


class IO {
    static byte[] buf = new byte[2048];
    static int index, total;
    static InputStream in;
    static BufferedWriter bw;


    IO(InputStream is, OutputStream os) {
        try {
            in = is;
            bw = new BufferedWriter(new OutputStreamWriter(os));
        } catch (Exception e) {
        }
    }

    IO(String inputFile, String outputFile) {
        try {
            in = new FileInputStream(inputFile);
            bw = new BufferedWriter(new OutputStreamWriter(
                    new FileOutputStream(outputFile)));
        } catch (Exception e) {
        }
    }

    int scan() throws Exception {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0)
                return -1;
        }
        return buf[index++];
    }

    String next() throws Exception {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan())
            sb.append((char) c);
        return sb.toString();
    }

    int nextInt() throws Exception {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+')
            c = scan();
        for (; c >= '0' && c <= '9'; c = scan())
            val = (val << 3) + (val << 1) + (c & 15);
        return neg ? -val : val;
    }

    long nextLong() throws Exception {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+')
            c = scan();
        for (; c >= '0' && c <= '9'; c = scan())
            val = (val << 3) + (val << 1) + (c & 15);
        return neg ? -val : val;
    }

    void print(Object a) throws Exception {
        bw.write(a.toString());
    }

    void printsp(Object a) throws Exception {
        print(a);
        bw.write(" ");
    }

    void println() throws Exception {
        bw.write("\n");
    }

    void println(Object a) throws Exception {
        print(a);
        println();
    }

    void flush() throws Exception {
        bw.flush();
        bw.close();
    }
}