#include <bits/stdc++.h>
using namespace std;
template <class A>
void read(vector<A>& v);
template <class A, size_t S>
void read(array<A, S>& a);
template <class T>
void read(T& x) {
  cin >> x;
}
void read(double& d) {
  string t;
  read(t);
  d = stod(t);
}
void read(long double& d) {
  string t;
  read(t);
  d = stold(t);
}
template <class H, class... T>
void read(H& h, T&... t) {
  read(h);
  read(t...);
}
template <class A>
void read(vector<A>& x) {
  for (auto& a : x) read(a);
}
template <class A, size_t S>
void read(array<A, S>& x) {
  for (auto& a : x) read(a);
}
string to_string(char c) { return string(1, c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return string(s); }
string to_string(string s) { return s; }
string to_string(vector<bool> v) {
  string res;
  for (int i = 0; i < (int)v.size(); ++i) res += char('0' + v[i]);
  return res;
}
template <size_t S>
string to_string(bitset<S> b) {
  string res;
  for (int i = 0; i < S; ++i) res += char('0' + b[i]);
  return res;
}
template <class T>
string to_string(T v) {
  bool f = 1;
  string res;
  for (auto x : v) {
    if (!f) res += ' ';
    f = 0;
    res += to_string(x);
  }
  return res;
}
template <class A>
void write(A x) {
  cout << to_string(x);
}
template <class H, class... T>
void write(const H& h, const T&... t) {
  write(h);
  write(t...);
}
void print() { write("\n"); }
template <class H, class... T>
void print(const H& h, const T&... t) {
  write(h);
  if (sizeof...(t)) write(' ');
  print(t...);
}
void DBG() { cerr << "]" << endl; }
template <class H, class... T>
void DBG(H h, T... t) {
  cerr << to_string(h);
  if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
const int MOD = 1e9 + 7;
const int N = 5e6 + 5;
const long long INF = 9e18;
const int M = 3e3 + 5;
struct x {
  int f, s, pos;
};
vector<x> f, s;
bool cmp1(x a, x b) { return a.s > b.s; }
bool cmp2(x a, x b) { return a.s < b.s; }
void solve() {
  int n;
  read(n);
  for (int i = 1; i <= n; ++i) {
    int a, b;
    read(a, b);
    x cur;
    cur.f = a, cur.s = b, cur.pos = i;
    if (a < b)
      f.push_back(cur);
    else
      s.push_back(cur);
  }
  sort(f.begin(), f.end(), cmp1);
  sort(s.begin(), s.end(), cmp2);
  vector<int> ans1, ans2;
  int l = MOD;
  for (auto cur : f) {
    if (l > cur.f) {
      ans1.push_back(cur.pos);
      l = cur.s;
    }
  }
  l = -1;
  for (auto cur : s) {
    if (l < cur.f) {
      ans2.push_back(cur.pos);
      l = cur.s;
    }
  }
  if ((int)ans1.size() < (int)ans2.size()) swap(ans1, ans2);
  cout << (int)ans1.size() << "\n";
  for (auto x : ans1) cout << x << " ";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  while (t--) {
    solve();
  }
  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>
using namespace std;
template <class A>
void read(vector<A>& v);
template <class A, size_t S>
void read(array<A, S>& a);
template <class T>
void read(T& x) {
  cin >> x;
}
void read(double& d) {
  string t;
  read(t);
  d = stod(t);
}
void read(long double& d) {
  string t;
  read(t);
  d = stold(t);
}
template <class H, class... T>
void read(H& h, T&... t) {
  read(h);
  read(t...);
}
template <class A>
void read(vector<A>& x) {
  for (auto& a : x) read(a);
}
template <class A, size_t S>
void read(array<A, S>& x) {
  for (auto& a : x) read(a);
}
string to_string(char c) { return string(1, c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return string(s); }
string to_string(string s) { return s; }
string to_string(vector<bool> v) {
  string res;
  for (int i = 0; i < (int)v.size(); ++i) res += char('0' + v[i]);
  return res;
}
template <size_t S>
string to_string(bitset<S> b) {
  string res;
  for (int i = 0; i < S; ++i) res += char('0' + b[i]);
  return res;
}
template <class T>
string to_string(T v) {
  bool f = 1;
  string res;
  for (auto x : v) {
    if (!f) res += ' ';
    f = 0;
    res += to_string(x);
  }
  return res;
}
template <class A>
void write(A x) {
  cout << to_string(x);
}
template <class H, class... T>
void write(const H& h, const T&... t) {
  write(h);
  write(t...);
}
void print() { write("\n"); }
template <class H, class... T>
void print(const H& h, const T&... t) {
  write(h);
  if (sizeof...(t)) write(' ');
  print(t...);
}
void DBG() { cerr << "]" << endl; }
template <class H, class... T>
void DBG(H h, T... t) {
  cerr << to_string(h);
  if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
const int MOD = 1e9 + 7;
const int N = 5e6 + 5;
const long long INF = 9e18;
const int M = 3e3 + 5;
struct x {
  int f, s, pos;
};
vector<x> f, s;
bool cmp1(x a, x b) { return a.s > b.s; }
bool cmp2(x a, x b) { return a.s < b.s; }
void solve() {
  int n;
  read(n);
  for (int i = 1; i <= n; ++i) {
    int a, b;
    read(a, b);
    x cur;
    cur.f = a, cur.s = b, cur.pos = i;
    if (a < b)
      f.push_back(cur);
    else
      s.push_back(cur);
  }
  sort(f.begin(), f.end(), cmp1);
  sort(s.begin(), s.end(), cmp2);
  vector<int> ans1, ans2;
  int l = MOD;
  for (auto cur : f) {
    if (l > cur.f) {
      ans1.push_back(cur.pos);
      l = cur.s;
    }
  }
  l = -1;
  for (auto cur : s) {
    if (l < cur.f) {
      ans2.push_back(cur.pos);
      l = cur.s;
    }
  }
  if ((int)ans1.size() < (int)ans2.size()) swap(ans1, ans2);
  cout << (int)ans1.size() << "\n";
  for (auto x : ans1) cout << x << " ";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}

```