<|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.

541. BR Privatization
Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Berland Railways (BR) is about to finish their existence as public property. Privatization is approaching.

Currently, BR consists of n stations, some pairs are connected by bidirectional roads. Between each pair of stations there is no more than one road and any road connects exactly two different stations.

Since each Berland railway network was developed independently, the topology of BR has an interesting form. BR consists of areas. Each area is a set of stations connected in a cycle in some order. Each area borders with exactly two different other areas and shares a single station with each of them. So exactly two stations in each area are shared by neighbouring areas. Thus, each station
either belongs to one area and has two roads going from it
or belongs to two neighbouring areas at the same time and has four roads going from it.
Since the BR form a connected network, one can say that the areas also form a single cycle of areas.

The figure below illustrates BR's possible structure.


In this case BR has 14 stations, 18 roads and consists of four areas numbered from 1 to 4:
the first one borders with the second and the third and has four stations;
the second one borders with the first and the fourth and has six stations;
the third one borders with the first and the fourth and has three stations;
the fourth one borders with the second and the third and has five stations.


Two major companies are planning to buy most of the BR stations. However the antitrust committee has its own requirements. No two stations connected by a road should belong to the same company. It frustrates the owners of the first and the second company, they may not even be able to purchase all the stations without violating this condition.

Both companies have decided to buy stations in such a way that the total number of stations purchased by both companies is maximal. If there are multiple ways for such distribution, they agree on any of them.

Help them to carry out their plans, write a program that finds the desired buying plan. Note that the information about BR is given to you as a list of stations and roads, but the information about areas is not explicitly defined.

Input
The first line contains a pair of integers n, m (6 ≤ n ≤ 105; 9 ≤ m ≤ 105), where n is the number of stations, and m is the number of roads. All stations are arbitrarily numbered from 1 to n. Then m lines follow, each containing a pair of integers ai,bi (1 ≤ ai,bi ≤ n; ai ≠ bi) and indicating the road that connects the stations with numbers ai and bi. The roads are given in arbitrary order.

BR consists of at least three areas, each contains at least three stations.

Output
In the first line print non-negative integer number n1 — the number of stations to be purchased by the first company. Then n1 numbers follow — the numbers of stations to be purchased by the first company.

In the second line print non-negative integer number n2 — the number of stations to be purchased by the second company. Then n2 numbers follow — the numbers of stations to be purchased by the second company.

If there are multiple solutions, print any of them.

Example(s)
sample input
sample output
14 18
1 2
1 4
1 7
1 8
2 4
3 4
3 14
4 5
5 6
6 14
7 11
7 10
7 9
8 9
10 12
11 14
12 13
13 14
6 2 5 7 8 12 14
7 1 3 6 9 10 11 13

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



Note
The first example corresponds to the illustration from the problem statement.

<|response|>
## 1. Abridged problem statement

You are given a connected undirected graph with a special structure:

- It is made of several simple cycles called **areas**.
- Areas form one big cycle of areas.
- Two neighboring areas share exactly one vertex.
- Every vertex has degree either:
  - `2`, if it belongs to exactly one area;
  - `4`, if it is shared by two neighboring areas.

Two companies want to buy as many vertices as possible. No two adjacent vertices may be bought by the same company.

Equivalently, after leaving some vertices unbought, the remaining graph must be **bipartite**.  
Find a maximum-size bipartite induced subgraph and output its two color classes.

---

## 2. Key observations needed to solve the problem

### Observation 1: The task is minimum vertex deletion to bipartite

If the bought vertices can be split between two companies, then the induced subgraph on bought vertices must be bipartite.

So we need to remove the minimum possible number of vertices so that the remaining graph becomes bipartite.

---

### Observation 2: Degree-4 vertices are area junctions

Because of the graph structure:

- degree-`4` vertices are shared between two neighboring areas;
- degree-`2` vertices are internal vertices of one area.

Each area has exactly two degree-`4` boundary vertices. Between them, the area contains two internally disjoint paths, called **arcs**.

For an area:

```text
junction A ---- arc 1 ---- junction B
junction A ---- arc 2 ---- junction B
```

The two arcs together form one cycle.

---

### Observation 3: We can reconstruct all areas

From each degree-`4` vertex, walk along every incident edge until another degree-`4` vertex is reached. All intermediate vertices have degree `2`.

Each such walk gives an arc between two junctions.

For every pair of junctions, there will be exactly two arcs between them. These two arcs form one area.

---

### Observation 4: Odd areas must be destroyed

If an area has odd size, it is an odd cycle. At least one vertex from it must be removed.

It is always optimal to remove a boundary junction instead of an internal vertex:

- removing an internal vertex destroys only one area;
- removing a junction destroys both adjacent areas.

Therefore, for odd areas, we only need to decide which junctions to remove.

---

### Observation 5: Odd areas become a covering problem on a cycle

The areas themselves form a cycle.

Deleting the junction between area `i` and area `i + 1` destroys both of these areas.

So:

- odd areas are marked positions on a cycle;
- choosing a junction covers the two neighboring positions;
- we need to cover all odd positions with the minimum number of chosen junctions.

For consecutive runs of odd areas, the optimal number of removals is:

```text
ceil(run_length / 2)
```

Special case: if all areas are odd, the whole cycle is one odd run, and the answer is:

```text
ceil(number_of_areas / 2)
```

---

### Observation 6: If all areas are even, there may still be one global odd cycle

Even if every individual area is even, there can be a large cycle going around the whole structure.

For each even area, both arcs have the same parity of length. Let that parity be `arc_parity`.

The parity of the big global cycle is:

```text
xor of arc_parity over all areas
```

If this parity is odd, deleting any one junction breaks this global odd cycle.

---

## 3. Full solution approach based on the observations

### Step 1: Build the graph

Store the graph using adjacency lists. Also store edge IDs, which helps us mark already processed boundary edges when reconstructing arcs.

---

### Step 2: Reconstruct arcs

For every degree-`4` vertex `j`:

1. For every incident edge `(j, x)`, if it was not processed yet:
2. Walk from `j` through degree-`2` vertices.
3. Stop when another degree-`4` vertex is reached.
4. Store the arc:
   - first junction;
   - second junction;
   - number of internal degree-`2` vertices.

The edge-length of this arc is:

```text
internal_count + 1
```

---

### Step 3: Reconstruct areas

Group arcs by unordered pair of endpoint junctions.

For each pair of junctions, there are exactly two arcs. Together they form one area.

If the two arcs have internal vertex counts `a` and `b`, then the area size is:

```text
2 + a + b
```

because the area consists of:

- two junctions;
- internal vertices of the first arc;
- internal vertices of the second arc.

---

### Step 4: Order areas around the meta-cycle

Each junction belongs to exactly two areas.

Build a list `junction -> areas containing it`.

Start from any area, then repeatedly move through one of its junctions to the neighboring area. This gives the cyclic order of all areas.

Also store:

```text
ordered_junctions[i]
```

which is the junction between ordered area `i` and ordered area `(i + 1) mod k`.

---

### Step 5: Choose junctions to delete

Let `is_odd[i]` tell whether ordered area `i` is odd.

#### Case 1: No odd areas

Compute the global cycle parity.

If it is odd, delete any one junction.  
Otherwise, delete nothing.

#### Case 2: All areas are odd

Pair neighboring areas greedily:

```text
(0, 1), (2, 3), ...
```

If one area remains unmatched, delete the wrap-around junction.

#### Case 3: Some areas are odd and some are even

Start after an even area. Then all odd areas appear as linear runs.

For each maximal run of odd areas of length `L`:

- pair neighboring odd areas inside the run;
- if one odd area remains, delete one of its boundary junctions.

This uses `ceil(L / 2)` deletions per run.

---

### Step 6: Bipartite coloring

Remove the selected junctions.

Then BFS/DFS-color the remaining graph with two colors.

The construction guarantees that the remaining graph is bipartite.

Output the two color classes.

---

### Complexity

Reconstructing arcs, reconstructing areas, choosing removed junctions, and BFS coloring are all linear.

```text
Time complexity:  O(n + m)
Memory complexity: O(n + m)
```

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

struct Arc {
    int j1, j2;          // endpoint junctions
    int internal_count;  // number of degree-2 vertices inside this arc
};

struct Area {
    int j1, j2;          // boundary junctions
    int size;            // number of vertices in this area cycle
    int arc_parity;      // parity of one arc length, meaningful if size is even
    bool odd;            // true if this area is an odd cycle
};

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

    int n, m;
    cin >> n >> m;

    // Adjacency list: pair(neighbor, edge_id)
    vector<vector<pair<int, int>>> adj(n + 1);

    for (int id = 0; id < m; id++) {
        int a, b;
        cin >> a >> b;

        adj[a].push_back({b, id});
        adj[b].push_back({a, id});
    }

    vector<int> deg(n + 1);
    for (int v = 1; v <= n; v++) {
        deg[v] = (int)adj[v].size();
    }

    /*
        Step 1: Recover all arcs.

        An arc is a maximal path:
            degree-4 junction -> degree-2 vertices -> degree-4 junction

        We start from every boundary edge incident to a junction.
        To avoid processing the same arc twice, we mark both boundary edges
        of the arc as seen.
    */
    vector<Arc> arcs;
    vector<char> seen_boundary_edge(m, false);

    for (int j = 1; j <= n; j++) {
        if (deg[j] != 4) {
            continue;
        }

        for (auto [x, start_edge] : adj[j]) {
            if (seen_boundary_edge[start_edge]) {
                continue;
            }

            int internal_count = 0;

            int prev = j;
            int cur = x;
            int last_edge = start_edge;

            // Walk through degree-2 vertices until another junction is reached.
            while (deg[cur] == 2) {
                internal_count++;

                auto e0 = adj[cur][0];
                auto e1 = adj[cur][1];

                int nxt, nxt_edge;

                if (e0.first == prev) {
                    nxt = e1.first;
                    nxt_edge = e1.second;
                } else {
                    nxt = e0.first;
                    nxt_edge = e0.second;
                }

                prev = cur;
                cur = nxt;
                last_edge = nxt_edge;
            }

            // cur is now the other degree-4 junction.
            seen_boundary_edge[start_edge] = true;
            seen_boundary_edge[last_edge] = true;

            arcs.push_back({j, cur, internal_count});
        }
    }

    /*
        Step 2: Group arcs by unordered pair of endpoint junctions.

        Exactly two arcs with the same endpoint pair form one area.
    */
    unordered_map<long long, vector<int>> by_pair;
    by_pair.reserve(arcs.size() * 2 + 10);

    auto make_key = [&](int a, int b) -> long long {
        if (a > b) swap(a, b);
        return 1LL * a * (n + 1) + b;
    };

    for (int i = 0; i < (int)arcs.size(); i++) {
        int a = arcs[i].j1;
        int b = arcs[i].j2;
        long long key = make_key(a, b);
        by_pair[key].push_back(i);
    }

    /*
        Step 3: Build the list of areas.
    */
    vector<Area> areas;

    for (auto &entry : by_pair) {
        vector<int> ids = entry.second;

        // Guaranteed by the graph structure.
        int id1 = ids[0];
        int id2 = ids[1];

        int a = min(arcs[id1].j1, arcs[id1].j2);
        int b = max(arcs[id1].j1, arcs[id1].j2);

        int len1_internal = arcs[id1].internal_count;
        int len2_internal = arcs[id2].internal_count;

        int size = 2 + len1_internal + len2_internal;

        Area ar;
        ar.j1 = a;
        ar.j2 = b;
        ar.size = size;
        ar.odd = (size % 2 == 1);

        // Edge length of an arc is internal_count + 1.
        ar.arc_parity = (len1_internal + 1) % 2;

        areas.push_back(ar);
    }

    int k = (int)areas.size();

    /*
        Step 4: For every junction, store which two areas contain it.
    */
    vector<vector<int>> junction_areas(n + 1);

    for (int i = 0; i < k; i++) {
        junction_areas[areas[i].j1].push_back(i);
        junction_areas[areas[i].j2].push_back(i);
    }

    /*
        Step 5: Order areas around the meta-cycle.
    */
    vector<int> area_order;
    area_order.reserve(k);

    int cur_area = 0;
    area_order.push_back(cur_area);

    // Choose one of area 0's junctions as the direction.
    int next_junction = areas[0].j2;

    while ((int)area_order.size() < k) {
        vector<int> &v = junction_areas[next_junction];

        // Move to the other area sharing this junction.
        int next_area = (v[0] == cur_area) ? v[1] : v[0];

        area_order.push_back(next_area);

        int entered_through = next_junction;

        // Leave next_area through its other junction.
        if (areas[next_area].j1 == entered_through) {
            next_junction = areas[next_area].j2;
        } else {
            next_junction = areas[next_area].j1;
        }

        cur_area = next_area;
    }

    /*
        ordered_junctions[i] is the junction between:
            area_order[i] and area_order[(i + 1) % k]
    */
    vector<int> ordered_junctions(k);

    for (int i = 0; i < k; i++) {
        int a = area_order[i];
        int b = area_order[(i + 1) % k];

        if (areas[a].j1 == areas[b].j1 || areas[a].j1 == areas[b].j2) {
            ordered_junctions[i] = areas[a].j1;
        } else {
            ordered_junctions[i] = areas[a].j2;
        }
    }

    /*
        Step 6: Decide which junctions to remove.
    */
    vector<char> is_odd(k, false);

    for (int i = 0; i < k; i++) {
        is_odd[i] = areas[area_order[i]].odd;
    }

    int odd_count = 0;
    for (int i = 0; i < k; i++) {
        odd_count += is_odd[i];
    }

    vector<char> remove_junction(k, false);

    if (odd_count == 0) {
        /*
            All local area cycles are even.

            The only possible obstruction is the large global cycle.
            Its parity is xor of arc parities.
        */
        int macro_parity = 0;

        for (int i = 0; i < k; i++) {
            macro_parity ^= areas[area_order[i]].arc_parity;
        }

        if (macro_parity == 1) {
            // Delete any one junction to break the global odd cycle.
            remove_junction[0] = true;
        }
    } else if (odd_count == k) {
        /*
            Every area is odd.

            Pair neighboring areas:
                (0, 1), (2, 3), ...
        */
        for (int i = 0; i + 1 < k; i += 2) {
            remove_junction[i] = true;
        }

        // If k is odd, one odd area remains.
        if (k % 2 == 1) {
            remove_junction[k - 1] = true;
        }
    } else {
        /*
            There is at least one even area.

            Start from an even position so odd areas become linear runs.
        */
        int start = 0;
        while (is_odd[start]) {
            start = (start + 1) % k;
        }

        int i = 0;

        while (i < k) {
            int pos = (start + i) % k;

            if (!is_odd[pos]) {
                i++;
                continue;
            }

            // Found a run of consecutive odd areas.
            int run_len = 0;

            while (i + run_len < k) {
                int cur_pos = (start + i + run_len) % k;

                if (!is_odd[cur_pos]) {
                    break;
                }

                run_len++;
            }

            // Pair odd areas inside this run.
            for (int j = 0; j + 1 < run_len; j += 2) {
                int p = (start + i + j) % k;

                // Delete junction between p and p + 1.
                remove_junction[p] = true;
            }

            // If one odd area remains, cover it with its right junction.
            if (run_len % 2 == 1) {
                int last = (start + i + run_len - 1) % k;
                remove_junction[last] = true;
            }

            i += run_len;
        }
    }

    /*
        Convert chosen junction positions to actual vertices.
    */
    vector<char> removed(n + 1, false);

    for (int i = 0; i < k; i++) {
        if (remove_junction[i]) {
            removed[ordered_junctions[i]] = true;
        }
    }

    /*
        Step 7: Bipartite-color the remaining graph.
    */
    vector<int> color(n + 1, -1);

    for (int s = 1; s <= n; s++) {
        if (removed[s] || color[s] != -1) {
            continue;
        }

        queue<int> q;
        q.push(s);
        color[s] = 0;

        while (!q.empty()) {
            int v = q.front();
            q.pop();

            for (auto [u, edge_id] : adj[v]) {
                if (removed[u]) {
                    continue;
                }

                if (color[u] == -1) {
                    color[u] = 1 - color[v];
                    q.push(u);
                }
            }
        }
    }

    vector<int> company1, company2;

    for (int v = 1; v <= n; v++) {
        if (color[v] == 0) {
            company1.push_back(v);
        } else if (color[v] == 1) {
            company2.push_back(v);
        }
    }

    cout << company1.size();
    for (int v : company1) {
        cout << ' ' << v;
    }
    cout << '\n';

    cout << company2.size();
    for (int v : company2) {
        cout << ' ' << v;
    }
    cout << '\n';

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys
from collections import defaultdict, deque


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))

    n = data[0]
    m = data[1]

    # Adjacency list stores pairs:
    #   (neighbor, edge_id)
    adj = [[] for _ in range(n + 1)]

    ptr = 2
    for edge_id in range(m):
        a = data[ptr]
        b = data[ptr + 1]
        ptr += 2

        adj[a].append((b, edge_id))
        adj[b].append((a, edge_id))

    deg = [0] * (n + 1)
    for v in range(1, n + 1):
        deg[v] = len(adj[v])

    # ------------------------------------------------------------
    # Step 1: Recover arcs.
    #
    # An arc is:
    #   degree-4 junction -> degree-2 vertices -> degree-4 junction
    # ------------------------------------------------------------

    arcs = []
    # Each arc has:
    #   (junction1, junction2, internal_degree_2_vertex_count)

    seen_boundary_edge = [False] * m

    for j in range(1, n + 1):
        if deg[j] != 4:
            continue

        for x, start_edge in adj[j]:
            if seen_boundary_edge[start_edge]:
                continue

            internal_count = 0

            prev = j
            cur = x
            last_edge = start_edge

            # Walk until another junction is reached.
            while deg[cur] == 2:
                internal_count += 1

                (to0, edge0), (to1, edge1) = adj[cur]

                if to0 == prev:
                    nxt = to1
                    nxt_edge = edge1
                else:
                    nxt = to0
                    nxt_edge = edge0

                prev = cur
                cur = nxt
                last_edge = nxt_edge

            # cur is now the other degree-4 junction.
            seen_boundary_edge[start_edge] = True
            seen_boundary_edge[last_edge] = True

            arcs.append((j, cur, internal_count))

    # ------------------------------------------------------------
    # Step 2: Group arcs by their unordered pair of junctions.
    #
    # Two arcs with the same endpoint pair form one area.
    # ------------------------------------------------------------

    by_pair = defaultdict(list)

    for i, (j1, j2, internal_count) in enumerate(arcs):
        if j1 > j2:
            j1, j2 = j2, j1

        by_pair[(j1, j2)].append(i)

    # ------------------------------------------------------------
    # Step 3: Build areas.
    # ------------------------------------------------------------

    areas = []
    # Each area is represented as a dictionary:
    #   {
    #       "j1": first junction,
    #       "j2": second junction,
    #       "size": number of vertices in the cycle,
    #       "odd": whether the area is odd,
    #       "arc_parity": parity of one arc length
    #   }

    for (j1, j2), ids in by_pair.items():
        id1 = ids[0]
        id2 = ids[1]

        len1_internal = arcs[id1][2]
        len2_internal = arcs[id2][2]

        size = 2 + len1_internal + len2_internal

        # Edge length of an arc is internal_count + 1.
        arc_parity = (len1_internal + 1) % 2

        areas.append({
            "j1": j1,
            "j2": j2,
            "size": size,
            "odd": size % 2 == 1,
            "arc_parity": arc_parity,
        })

    k = len(areas)

    # ------------------------------------------------------------
    # Step 4: For each junction, store the two areas that contain it.
    # ------------------------------------------------------------

    junction_areas = [[] for _ in range(n + 1)]

    for i, area in enumerate(areas):
        junction_areas[area["j1"]].append(i)
        junction_areas[area["j2"]].append(i)

    # ------------------------------------------------------------
    # Step 5: Order areas around the meta-cycle.
    # ------------------------------------------------------------

    area_order = [0]

    cur_area = 0
    next_junction = areas[0]["j2"]

    while len(area_order) < k:
        two_areas = junction_areas[next_junction]

        # Move to the other area sharing this junction.
        if two_areas[0] == cur_area:
            next_area = two_areas[1]
        else:
            next_area = two_areas[0]

        area_order.append(next_area)

        entered_through = next_junction

        # Leave through the other junction of next_area.
        if areas[next_area]["j1"] == entered_through:
            next_junction = areas[next_area]["j2"]
        else:
            next_junction = areas[next_area]["j1"]

        cur_area = next_area

    # ordered_junctions[i] is the junction between:
    #   area_order[i] and area_order[(i + 1) % k]
    ordered_junctions = [0] * k

    for i in range(k):
        a = area_order[i]
        b = area_order[(i + 1) % k]

        if areas[a]["j1"] == areas[b]["j1"] or areas[a]["j1"] == areas[b]["j2"]:
            ordered_junctions[i] = areas[a]["j1"]
        else:
            ordered_junctions[i] = areas[a]["j2"]

    # ------------------------------------------------------------
    # Step 6: Choose junctions to remove.
    # ------------------------------------------------------------

    is_odd = [False] * k

    for i in range(k):
        is_odd[i] = areas[area_order[i]]["odd"]

    odd_count = sum(is_odd)

    # remove_junction[i] means:
    #   delete ordered_junctions[i],
    #   the junction between area i and area i + 1
    remove_junction = [False] * k

    if odd_count == 0:
        # All local area cycles are even.
        # Check the global cycle parity.
        macro_parity = 0

        for i in range(k):
            macro_parity ^= areas[area_order[i]]["arc_parity"]

        if macro_parity == 1:
            remove_junction[0] = True

    elif odd_count == k:
        # Every area is odd.
        # Pair neighboring odd areas greedily.
        i = 0
        while i + 1 < k:
            remove_junction[i] = True
            i += 2

        # If one odd area remains, cover it using the wrap-around junction.
        if k % 2 == 1:
            remove_junction[k - 1] = True

    else:
        # Some areas are odd and some are even.
        # Start from an even area so odd areas form linear runs.
        start = 0
        while is_odd[start]:
            start = (start + 1) % k

        i = 0

        while i < k:
            pos = (start + i) % k

            if not is_odd[pos]:
                i += 1
                continue

            # Found a run of consecutive odd areas.
            run_len = 0

            while i + run_len < k:
                cur_pos = (start + i + run_len) % k

                if not is_odd[cur_pos]:
                    break

                run_len += 1

            # Pair adjacent odd areas inside the run.
            j = 0
            while j + 1 < run_len:
                p = (start + i + j) % k

                # Delete the junction between p and p + 1.
                remove_junction[p] = True

                j += 2

            # If one odd area remains, delete one of its boundary junctions.
            if run_len % 2 == 1:
                last = (start + i + run_len - 1) % k
                remove_junction[last] = True

            i += run_len

    # Convert chosen junction positions into actual removed vertices.
    removed = [False] * (n + 1)

    for i in range(k):
        if remove_junction[i]:
            removed[ordered_junctions[i]] = True

    # ------------------------------------------------------------
    # Step 7: Bipartite-color the remaining graph.
    # ------------------------------------------------------------

    color = [-1] * (n + 1)

    for s in range(1, n + 1):
        if removed[s] or color[s] != -1:
            continue

        q = deque([s])
        color[s] = 0

        while q:
            v = q.popleft()

            for u, edge_id in adj[v]:
                if removed[u]:
                    continue

                if color[u] == -1:
                    color[u] = 1 - color[v]
                    q.append(u)

    company1 = []
    company2 = []

    for v in range(1, n + 1):
        if color[v] == 0:
            company1.append(v)
        elif color[v] == 1:
            company2.append(v)

    out = []

    out.append(
        str(len(company1)) +
        ("" if not company1 else " " + " ".join(map(str, company1)))
    )

    out.append(
        str(len(company2)) +
        ("" if not company2 else " " + " ".join(map(str, company2)))
    )

    sys.stdout.write("\n".join(out))


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