#include <bits/stdc++.h>
using namespace std;
const long long maxx = 2e6 + 1314;
long long read() {
  long long k;
  scanf("%lld", &k);
  return k;
}
long long p[maxx], n;
long long x[maxx], y[maxx], top;
void init(long long X, long long Y) {
  x[++top] = X;
  y[top] = Y;
}
long long idx[maxx];
struct edge {
  long long x, y, id;
} A[maxx], w[maxx];
bool my(edge a, edge b) { return a.y > b.y; }
bool mt(edge a, edge b) { return a.y < b.y; }
long long ans1;
vector<edge> Aa[3];
long long ans[3];
void slove(long long f) {
  if (f == 1)
    sort(w + 1, w + 1 + top, my);
  else
    sort(w + 1, w + 1 + top, mt);
  ans[f]++;
  long long Max = w[1].y;
  Aa[f].push_back(w[1]);
  if (f == 1)
    for (long long i = 2; i <= top; i++)
      if (Max > w[i].x) ans[f]++, Max = w[i].y, Aa[1].push_back(w[i]);
  if (f == 2)
    for (long long i = 2; i <= top; i++)
      if (Max < w[i].x) ans[f]++, Max = w[i].y, Aa[2].push_back(w[i]);
  return;
}
signed main() {
  n = read();
  for (long long i = 1; i <= n; i++)
    A[i].x = read(), A[i].y = read(), A[i].id = i;
  for (long long i = 1; i <= n; i++)
    if (A[i].x < A[i].y) w[++top] = A[i];
  slove(1);
  top = 0;
  for (long long i = 1; i <= n; i++)
    if (A[i].x > A[i].y) w[++top] = A[i];
  slove(2);
  if (ans[2] > ans[1]) swap(ans[1], ans[2]), swap(Aa[1], Aa[2]);
  long long len = Aa[1].size();
  cout << ans[1] << endl;
  for (long long i = 0; i < len; i++) cout << Aa[1][i].id << ' ';
  cout << endl;
  return 0;
}

### Prompt

Please create a solution in Cpp to the following 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long maxx = 2e6 + 1314;
long long read() {
  long long k;
  scanf("%lld", &k);
  return k;
}
long long p[maxx], n;
long long x[maxx], y[maxx], top;
void init(long long X, long long Y) {
  x[++top] = X;
  y[top] = Y;
}
long long idx[maxx];
struct edge {
  long long x, y, id;
} A[maxx], w[maxx];
bool my(edge a, edge b) { return a.y > b.y; }
bool mt(edge a, edge b) { return a.y < b.y; }
long long ans1;
vector<edge> Aa[3];
long long ans[3];
void slove(long long f) {
  if (f == 1)
    sort(w + 1, w + 1 + top, my);
  else
    sort(w + 1, w + 1 + top, mt);
  ans[f]++;
  long long Max = w[1].y;
  Aa[f].push_back(w[1]);
  if (f == 1)
    for (long long i = 2; i <= top; i++)
      if (Max > w[i].x) ans[f]++, Max = w[i].y, Aa[1].push_back(w[i]);
  if (f == 2)
    for (long long i = 2; i <= top; i++)
      if (Max < w[i].x) ans[f]++, Max = w[i].y, Aa[2].push_back(w[i]);
  return;
}
signed main() {
  n = read();
  for (long long i = 1; i <= n; i++)
    A[i].x = read(), A[i].y = read(), A[i].id = i;
  for (long long i = 1; i <= n; i++)
    if (A[i].x < A[i].y) w[++top] = A[i];
  slove(1);
  top = 0;
  for (long long i = 1; i <= n; i++)
    if (A[i].x > A[i].y) w[++top] = A[i];
  slove(2);
  if (ans[2] > ans[1]) swap(ans[1], ans[2]), swap(Aa[1], Aa[2]);
  long long len = Aa[1].size();
  cout << ans[1] << endl;
  for (long long i = 0; i < len; i++) cout << Aa[1][i].id << ' ';
  cout << endl;
  return 0;
}

```