<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

521. "North-East"
Time limit per test: 0.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

The popular music band of international fame "North-East" is coming to Berland! This news has spread all over the country, so numerous fans are now ready to rush and buy all the tickets!

At present the fans still don't know in which cities the band plans to give concerts. The only thing is known at the moment is that the band will visit several cities, and as their name says, they will strictly move north and east when going to the next city. In other words when the band moves from city i to city j, city j is always located northward and eastward of the city i.

It's also known that the tour is planned in such a way that the maximum possible number of cities will be visited. The musicians refuse to reveal other details. As you know, fans always get ready for the arrival of their idols, so they would appreciate any single detail about possible movements of their favorite musicians.

Your task is to help the fans and find two lists of cities — A and B. The first list A should contain the cities, which the band might visit during the tour. The second list B should contain the cities, which the band will have to visit for sure during the tour.

Input
The first line of input contains a single integer n (1 ≤ n ≤ 105) — amount of cities in the country. The following n lines contain coordinates of the cities. Each line contains a pair of integers xi, yi (-106 ≤ xi, yi ≤ 106) — the coordinates of the i-th city. Ox axis is directed west-to-east, and Oy axis — south-to-north. No two given cities will be located at the same point.

Output
Print the required list A to the first line of output and B to the second line. Each list should start with the amount of cities in it, followed by the indices of cities in increasing order. Cities are numbered from 1 to n.

Example(s)
sample input
sample output
5
3 2
1 1
5 5
2 3
4 4
5 1 2 3 4 5
3 2 3 5

sample input
sample output
5
1 1
10 10
5 6
10 1
6 5
4 1 2 3 5
2 1 2

<|response|>
1. Abridged problem statement
You have n distinct points (cities) with integer coordinates (x, y). A "tour" is a sequence of cities in which both x and y strictly increase at each step. Let L be the maximum length of any such tour.
- List A: all city indices that appear in at least one tour of length L.
- List B: all city indices that appear in every tour of length L.
Output A and B: each line begins with the list size, then the sorted indices.

2. Key observations
- This is a 2D longest increasing subsequence (LIS) problem: we need the LIS ending at each point (up_dp) and the LIS starting from each point if we reverse the x-order (down_dp).
- For each city i, up_dp[i] = length of longest increasing-both-coordinates path ending at i.
- Similarly, down_dp[i] = length of longest path starting at i when we traverse cities by decreasing x (but still require increasing y).
- If a city i lies on some maximum-length tour, then up_dp[i] + down_dp[i] − 1 = L.
- Among those cities, at each "level" k = up_dp[i], if exactly one city has that level, it must be in every maximum tour at position k.

3. Full solution approach
a) Coordinate compression on y:
   - Collect all y values, sort uniquely, map each y to a rank in 0…M−1.
b) Compute up_dp:
   - Sort cities by x ascending; group ties by the same x (cities with equal x cannot follow each other).
   - Maintain a segment tree over y-ranks for range-maximum queries.
   - For each batch, query the segment tree for max over [0 … ry−1], set up_dp = 1 + that max, then after the full batch update the tree at each ry.
c) Compute down_dp:
   - Sort cities by x descending; same batching approach.
   - Query the segment tree for max over [ry+1 … M−1] (the suffix of larger y-ranks).
   - Set down_dp = 1 + that max, then update the tree after the batch.
d) Let L = max_i (up_dp[i] + down_dp[i] − 1).
e) Build List A = { i | up_dp[i] + down_dp[i] − 1 == L }.
f) Group A by level k = up_dp[i]. For each k, if the group size is 1, that city is forced → add to B.
g) Sort A and B and print.

Complexity: O(n log n) for sorting, coordinate compression, and segment-tree operations.

4. C++ implementation with detailed comments
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

template<class T, T (*merge)(T, T), T (*e)()>
class SegmentTree {
  private:
    int n, size;
    vector<T> tr;
    void pull(int x) { tr[x] = merge(tr[2 * x], tr[2 * x + 1]); }

  public:
    SegmentTree() { init(vector<T>()); }
    SegmentTree(int _n) { init(vector<T>(_n, e())); }
    SegmentTree(const vector<T>& _a) { init(_a); }
    void init(const vector<T>& _a) {
        n = _a.size();
        size = 1;
        while(size < n) {
            size <<= 1;
        }
        tr.assign(2 * size, e());
        for(int i = 0; i < n; i++) {
            tr[size + i] = _a[i];
        }
        for(int i = size - 1; i > 0; i--) {
            pull(i);
        }
    }
    void update(int pos, T val) {
        pos += size;
        tr[pos] = val;
        for(pos >>= 1; pos > 0; pos >>= 1) {
            pull(pos);
        }
    }
    T get_pos(int pos) { return tr[pos + size]; }
    T query(int l, int r) {
        T ansl = e(), ansr = e();
        for(l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
            if(l & 1) {
                ansl = merge(ansl, tr[l++]);
            }
            if(r & 1) {
                ansr = merge(tr[--r], ansr);
            }
        }
        return merge(ansl, ansr);
    }
    T query_all() { return tr[1]; }
    template<bool (*f)(T)>
    int max_right(int l) const {
        return max_right(l, [](T x) { return f(x); });
    }
    template<class F>
    int max_right(int l, F f) const {
        if(l == n) {
            return n;
        }
        l += size;
        T sm = e();
        do {
            while(l % 2 == 0) {
                l >>= 1;
            }
            if(!f(merge(sm, tr[l]))) {
                while(l < size) {
                    l = (2 * l);
                    if(f(merge(sm, tr[l]))) {
                        sm = merge(sm, tr[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = merge(sm, tr[l]);
            l++;
        } while((l & -l) != l);
        return n;
    }
    template<bool (*f)(T)>
    int min_left(int r) const {
        return min_left(r, [](T x) { return f(x); });
    }
    template<class F>
    int min_left(int r, F f) const {
        if(r == -1) {
            return 0;
        }
        r += size + 1;
        T sm = e();
        do {
            r--;
            while(r > 1 && (r % 2)) {
                r >>= 1;
            }
            if(!f(merge(tr[r], sm))) {
                while(r < size) {
                    r = (2 * r + 1);
                    if(f(merge(tr[r], sm))) {
                        sm = merge(tr[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = merge(tr[r], sm);
        } while((r & -r) != r);
        return 0;
    }
};

int op(int a, int b) { return max(a, b); }

int id() { return 0; }

struct Point {
    int id, ry;
    int64_t x, y;
};

int N;
vector<Point> points;
vector<int64_t> y_coords;
vector<int> up_dp, down_dp;

void read() {
    cin >> N;
    points.resize(N);
    for(int i = 0; i < N; i++) {
        cin >> points[i].x >> points[i].y;
        points[i].id = i + 1;
        y_coords.push_back(points[i].y);
    }
}

void compress_coordinates() {
    sort(y_coords.begin(), y_coords.end());
    y_coords.erase(unique(y_coords.begin(), y_coords.end()), y_coords.end());

    for(auto& p: points) {
        p.ry = lower_bound(y_coords.begin(), y_coords.end(), p.y) -
               y_coords.begin();
    }
}

void compute_up_dp() {
    vector<Point> sorted_points = points;
    sort(
        sorted_points.begin(), sorted_points.end(),
        [](const Point& a, const Point& b) { return a.x < b.x; }
    );

    SegmentTree<int, &op, &id> seg_tree(y_coords.size());
    up_dp.assign(N + 1, 0);

    int idx = 0;
    while(idx < N) {
        int64_t current_x = sorted_points[idx].x;
        vector<pair<int, int>> group;

        while(idx < N && sorted_points[idx].x == current_x) {
            group.push_back({sorted_points[idx].ry, sorted_points[idx].id});
            idx++;
        }

        vector<int> dp_values(group.size());
        for(size_t j = 0; j < group.size(); j++) {
            int ry = group[j].first;
            int max_prev = (ry == 0 ? 0 : seg_tree.query(0, ry - 1));
            dp_values[j] = 1 + max_prev;
        }

        for(size_t j = 0; j < group.size(); j++) {
            int ry = group[j].first;
            int current_val = seg_tree.get_pos(ry);
            seg_tree.update(ry, max(current_val, dp_values[j]));
            up_dp[group[j].second] = dp_values[j];
        }
    }
}

void compute_down_dp() {
    vector<Point> sorted_points = points;
    sort(
        sorted_points.begin(), sorted_points.end(),
        [](const Point& a, const Point& b) { return a.x > b.x; }
    );

    SegmentTree<int, &op, &id> seg_tree(y_coords.size());
    down_dp.assign(N + 1, 0);

    int idx = 0;
    while(idx < N) {
        int64_t current_x = sorted_points[idx].x;
        vector<pair<int, int>> group;

        while(idx < N && sorted_points[idx].x == current_x) {
            group.push_back({sorted_points[idx].ry, sorted_points[idx].id});
            idx++;
        }

        vector<int> dp_values(group.size());
        for(size_t j = 0; j < group.size(); j++) {
            int ry = group[j].first;
            int max_prev =
                (ry + 1 < (int)y_coords.size()
                     ? seg_tree.query(ry + 1, y_coords.size() - 1)
                     : 0);
            dp_values[j] = 1 + max_prev;
        }

        for(size_t j = 0; j < group.size(); j++) {
            int ry = group[j].first;
            int current_val = seg_tree.get_pos(ry);
            seg_tree.update(ry, max(current_val, dp_values[j]));
            down_dp[group[j].second] = dp_values[j];
        }
    }
}

void solve() {
    // A tour moves strictly north-east, so it is a strictly increasing
    // chain in both x and y: a longest strictly-increasing (in x and y)
    // subsequence of the points. We need the cities that lie on some
    // longest chain (list A) and those on every longest chain (list B).
    //
    // up_dp[i] = length of the longest chain ending at city i; computed by
    // sweeping points by increasing x (ties grouped so equal-x points
    // cannot chain to each other) and querying a max-segment-tree over
    // compressed y for the best chain among smaller y. down_dp[i] is the
    // symmetric quantity sweeping by decreasing x and querying larger y.
    //
    // City i is on some longest chain iff up_dp[i] + down_dp[i] - 1 equals
    // the global maximum chain length: that is list A. Within a longest
    // chain a city occupies a fixed "level" = up_dp[i]. A city is on every
    // longest chain iff it is the only critical city at its level, since
    // otherwise some longest chain could route through a different city at
    // that level: that is list B. Both lists are printed in increasing
    // index order, each prefixed by its size.

    compress_coordinates();
    compute_up_dp();
    compute_down_dp();

    int max_path_length = 0;
    for(int i = 1; i <= N; i++) {
        max_path_length = max(max_path_length, up_dp[i] + down_dp[i] - 1);
    }

    vector<int> critical_points;
    for(int i = 1; i <= N; i++) {
        if(up_dp[i] + down_dp[i] - 1 == max_path_length) {
            critical_points.push_back(i);
        }
    }

    sort(critical_points.begin(), critical_points.end());
    cout << critical_points.size();
    for(int point: critical_points) {
        cout << ' ' << point;
    }
    cout << '\n';

    map<int, vector<int>> groups_by_up;
    for(int id: critical_points) {
        groups_by_up[up_dp[id]].push_back(id);
    }

    vector<int> unique_critical_points;
    for(auto& p: groups_by_up) {
        if(p.second.size() == 1) {
            unique_critical_points.push_back(p.second[0]);
        }
    }

    sort(unique_critical_points.begin(), unique_critical_points.end());
    cout << unique_critical_points.size();
    for(int point: unique_critical_points) {
        cout << ' ' << point;
    }
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with detailed comments
```python
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

# Fenwick (BIT) for prefix-max queries and point updates
class FenwickMax:
    def __init__(self, n):
        self.n = n
        self.fw = [0] * (n+1)
    # update index i (1-based) to max(current, v)
    def update(self, i, v):
        while i <= self.n:
            if self.fw[i] < v:
                self.fw[i] = v
            i += i & -i
    # query max on [1..i]
    def query(self, i):
        res = 0
        while i > 0:
            if self.fw[i] > res:
                res = self.fw[i]
            i -= i & -i
        return res

def main():
    n = int(input())
    pts = []
    ys = []
    for idx in range(1, n+1):
        x, y = map(int, input().split())
        pts.append([x, y, idx])
        ys.append(y)
    # compress y
    ys_sorted = sorted(set(ys))
    m = len(ys_sorted)
    for p in pts:
        # rank 1..m
        p.append(1 + ys_sorted.index(p[1]))

    # up_dp: LIS ending at each point
    up_dp = [0]*(n+1)
    # sort by x increasing
    pts.sort(key=lambda p: p[0])
    ft = FenwickMax(m)

    i = 0
    while i < n:
        x0 = pts[i][0]
        batch = []
        # gather same x
        while i < n and pts[i][0] == x0:
            batch.append(pts[i])
            i += 1
        # compute dp for batch
        vals = []
        for _, _, idx, ry in batch:
            # max dp among ry'<ry -> query(ry-1)
            best = ft.query(ry-1)
            vals.append(1 + best)
        # update
        for (_, _, idx, ry), v in zip(batch, vals):
            # record dp
            up_dp[idx] = v
        for (_, _, idx, ry), v in zip(batch, vals):
            ft.update(ry, v)

    # down_dp: LIS starting at each point going x-decreasing
    down_dp = [0]*(n+1)
    # we want y increasing but x decreasing
    # equivalently reverse x, and for y suffix queries, mirror ry
    # mirror ry -> mr = m+1-ry
    for p in pts:
        p.append(m+1 - p[3])  # p[4] = mirrored ry

    # sort by x descending
    pts.sort(key=lambda p: -p[0])
    ft = FenwickMax(m)
    i = 0
    while i < n:
        x0 = pts[i][0]
        batch = []
        while i < n and pts[i][0] == x0:
            batch.append(pts[i])
            i += 1
        vals = []
        for _, _, idx, ry, mry in batch:
            # we want max over original ry'>ry -> mirrored index < mry
            best = ft.query(mry-1)
            vals.append(1 + best)
        for (_, _, idx, ry, mry), v in zip(batch, vals):
            down_dp[idx] = v
        for (_, _, idx, ry, mry), v in zip(batch, vals):
            ft.update(mry, v)

    # compute global max length L
    L = 0
    for i in range(1, n+1):
        L = max(L, up_dp[i] + down_dp[i] - 1)

    # List A: those on some maximum path
    A = [i for i in range(1, n+1) if up_dp[i] + down_dp[i] - 1 == L]
    A.sort()
    # List B: forced positions
    from collections import defaultdict
    bylev = defaultdict(list)
    for x in A:
        bylev[ up_dp[x] ].append(x)
    B = [v[0] for k,v in bylev.items() if len(v)==1]
    B.sort()

    # output
    print(len(A), *A)
    print(len(B), *B)

if __name__ == "__main__":
    main()
```

Explanation of steps is embedded as comments in the code. Both implementations run in O(n log n) time and O(n) memory, suitable for n up to 10^5.
