1. Abridged Problem Statement

You are given n distinct cities on a plane with coordinates (xi, yi). A valid tour is a sequence of cities where both x and y strictly increase at each step. The band wants to maximize the number of cities visited; let L be this maximum length.
- List A: all city indices that appear in at least one longest tour of length L.
- List B: all city indices that appear in every longest tour.

Output A and B: each line starts with the count of cities, followed by their indices in ascending order.

2. Detailed Editorial

Overview
We need to find all points that can be on some longest strictly increasing-both-coordinates path (List A), and those that must be on every such path (List B). This is a 2D longest increasing subsequence (LIS) problem.

Steps
1. Coordinate Compression on y
   - Gather all y-coordinates, sort and unique them → ranks [0..M−1].
   - Replace each point's y with its rank ry.

2. Compute up_dp[i] = length of longest path ending at point i.
   - Sort points by x ascending. Process equal-x points in a batch (they cannot follow each other).
   - Maintain a segment tree over ry supporting max-query on [0..ry−1] and point-update at ry.
   - For each point in batch: up_dp = 1 + max_query(0, ry−1).
   - After computing dp for the batch, update the tree at each ry with its dp if larger.

3. Compute down_dp[i] = length of longest path starting at point i, going in decreasing x but still increasing y.
   - Sort points by x descending; similarly batch same x.
   - Use a segment tree on ry; query max over [ry+1..M−1] directly.
   - down_dp = 1 + max_query(ry+1, M−1). Update in batch.

4. Find L = max_i (up_dp[i] + down_dp[i] − 1).
   - List A: all i with up_dp[i] + down_dp[i] − 1 == L.

5. Find List B (must-visit).
   - In any length-L path, exactly one city has up_dp = k at position k.
   - Group critical points (those in A) by their up_dp value.
   - If a group for k has size 1, that city is forced at position k in every path. Collect these.

Complexities
- Sorting: O(n log n)
- Coordinate compression: O(n log n)
- Two passes of O(n log n) segment-tree operations
Overall O(n log n), feasible to n=1e5.

3. C++ Solution

```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;
}
```

4. Python Solution

```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()
```

5. Compressed Editorial

- Compress y-coordinates.
- up_dp: process points by x↑, batch equal-x points, use segment tree for max on y-prefix [0..ry−1], dp = 1+max(0..ry−1).
- down_dp: process x↓, batch equal-x, query segment tree for suffix max [ry+1..M−1], dp = 1+max(ry+1..M−1).
- L = max(up_dp+down_dp−1).
- A = indices with up_dp+down_dp−1 == L.
- B = in A, those with unique up_dp level (position) across all critical points.
