#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
long long dx[4] = {1, -1, 0, 0};
long long dy[4] = {0, 0, 1, -1};
const long long MOD = 2;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long fir, long long sec) {
  return (fir * sec) / (gcd(fir, sec));
}
long long fast_pow(long long a, long long b) {
  long long res = a, ret = 1;
  while (b > 0) {
    if (b % 2) ret = (ret * res) % MOD;
    res = (res * res) % MOD;
    b /= 2;
  }
  return ret;
}
const long long maxN = 3e5 + 7;
pair<pair<long long, long long>, long long> arr[maxN];
bool sortbyfir(const pair<pair<long long, long long>, long long> a,
               const pair<pair<long long, long long>, long long> b) {
  return (a.first.first > b.first.first);
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  time_t time_t1, time_t2;
  time_t1 = clock();
  long long t = 1;
  while (t--) {
    long long n;
    cin >> n;
    long long a, b;
    long long asc = 0;
    long long desc = 0;
    for (long long i = 0; i < n; ++i) {
      cin >> a >> b;
      if (a > b) {
        desc++;
      } else {
        asc++;
      }
      arr[i] = {{a, b}, i + 1};
    }
    std::vector<long long> ans;
    if (asc > desc) {
      sort(arr, arr + n, sortbyfir);
      for (long long i = 0; i < n; ++i) {
        ;
      }
      for (long long i = 0; i < n; ++i) {
        if (arr[i].first.first < arr[i].first.second) {
          ans.push_back(arr[i].second);
        }
      }
    } else {
      sort(arr, arr + n);
      for (long long i = 0; i < n; ++i) {
        ;
        if (arr[i].first.first > arr[i].first.second) {
          ans.push_back(arr[i].second);
        }
      }
    }
    cout << ans.size() << '\n';
    for (long long x : ans) {
      cout << x << " ";
    }
    cout << '\n';
  }
  time_t2 = clock();
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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.

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
long long dx[4] = {1, -1, 0, 0};
long long dy[4] = {0, 0, 1, -1};
const long long MOD = 2;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long fir, long long sec) {
  return (fir * sec) / (gcd(fir, sec));
}
long long fast_pow(long long a, long long b) {
  long long res = a, ret = 1;
  while (b > 0) {
    if (b % 2) ret = (ret * res) % MOD;
    res = (res * res) % MOD;
    b /= 2;
  }
  return ret;
}
const long long maxN = 3e5 + 7;
pair<pair<long long, long long>, long long> arr[maxN];
bool sortbyfir(const pair<pair<long long, long long>, long long> a,
               const pair<pair<long long, long long>, long long> b) {
  return (a.first.first > b.first.first);
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  time_t time_t1, time_t2;
  time_t1 = clock();
  long long t = 1;
  while (t--) {
    long long n;
    cin >> n;
    long long a, b;
    long long asc = 0;
    long long desc = 0;
    for (long long i = 0; i < n; ++i) {
      cin >> a >> b;
      if (a > b) {
        desc++;
      } else {
        asc++;
      }
      arr[i] = {{a, b}, i + 1};
    }
    std::vector<long long> ans;
    if (asc > desc) {
      sort(arr, arr + n, sortbyfir);
      for (long long i = 0; i < n; ++i) {
        ;
      }
      for (long long i = 0; i < n; ++i) {
        if (arr[i].first.first < arr[i].first.second) {
          ans.push_back(arr[i].second);
        }
      }
    } else {
      sort(arr, arr + n);
      for (long long i = 0; i < n; ++i) {
        ;
        if (arr[i].first.first > arr[i].first.second) {
          ans.push_back(arr[i].second);
        }
      }
    }
    cout << ans.size() << '\n';
    for (long long x : ans) {
      cout << x << " ";
    }
    cout << '\n';
  }
  time_t2 = clock();
  return 0;
}

```