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

---

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:

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

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

```
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:

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

---

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.

---

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 2 + a + b.

---

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 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: (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

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

---

4. C++ implementation with 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;
};

int n, m;
vector<vector<int>> adj;

void read() {
    cin >> n >> m;
    adj.assign(n + 1, {});
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
}

void solve() {
    // Stations split by degree: deg 2 are interior vertices of exactly one
    // area, deg 4 are junctions shared by two adjacent areas. Each area is a
    // cycle whose two junctions split its interior into two chains (arcs);
    // the areas themselves form a meta-cycle of length k whose edges are the
    // junctions.
    //
    // We want a proper 2-coloring of the induced subgraph after removing the
    // minimum number of stations, i.e. the remaining graph must be bipartite,
    // which means every surviving cycle must be even.
    //
    // For each area the two arcs have edge-lengths a, b with a + b = size;
    // when size is even, a and b share the same parity, call it arc_parity.
    // Walking the meta-cycle, the macro cycle (going around through one arc
    // of each area) has length parity equal to the XOR of arc_parity over
    // all areas.
    //
    // Removing a junction has two effects at once: both incident areas
    // become paths (always bipartite), and the macro cycle is broken. So a
    // junction removal is never worse than an interior removal:
    //
    //   - every odd area needs at least one of its incident junctions
    //     removed;
    //
    //   - pair adjacent odd areas along the meta-cycle and remove their
    //     shared junction (one removal kills two odd cycles);
    //
    //   - for an unmatched odd area, remove either of its two bounding
    //     junctions (covers one odd, plus collaterally an even neighbor
    //     which is fine).
    //
    // Minimum removals when there is at least one odd area equals
    // (#odd areas) - (max matching of adjacent odd pairs in the meta-cycle).
    //
    // If no area is odd, the only remaining obstacle is the macro cycle
    // parity; if it is 1, remove any single junction to break it.
    //
    // Implementation: arcs are recovered by walking from each junction edge
    // through interior vertices until hitting the next junction, with the
    // first edge incident to a junction marked on both walking directions
    // to deduplicate. Grouping arcs by unordered junction pair recovers the
    // areas - each pair has exactly two arcs that together form one area.
    // Each junction is in exactly two areas, so walking from area 0 via its
    // j2 side and always taking the "other" area at the current junction
    // traverses the meta-cycle, producing area_order[0..k-1] and
    // ordered_junctions[i] = the shared junction of area_order[i] and
    // area_order[(i+1) % k]. For the matching step, when the meta-cycle has
    // both odd and even positions, linearize starting at any even position
    // so each maximal run of consecutive odd positions is a contiguous
    // interval and pair them up greedily inside each run; when all
    // positions are odd (p == k) handle separately by pairing (0,1),(2,3),
    // ... and if k is odd take one more junction at the wrap-around for the
    // leftover. Finally BFS-2-color the graph minus the removed junctions;
    // by construction all surviving cycles are even, so coloring succeeds.

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

    struct Arc {
        int j1, j2;
        int interior_count;
    };

    vector<Arc> arcs;
    set<pair<int, int>> seen_first_edge;

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

        for(int x: adj[j]) {
            if(seen_first_edge.count({j, x})) {
                continue;
            }

            int interior_count = 0;
            int prev = j, cur = x;
            while(deg[cur] == 2) {
                interior_count++;
                int nxt = (adj[cur][0] == prev) ? adj[cur][1] : adj[cur][0];
                prev = cur;
                cur = nxt;
            }

            seen_first_edge.insert({j, x});
            seen_first_edge.insert({cur, prev});
            arcs.push_back({j, cur, interior_count});
        }
    }

    map<pair<int, int>, vector<int>> by_pair;
    for(int i = 0; i < (int)arcs.size(); i++) {
        int a = min(arcs[i].j1, arcs[i].j2);
        int b = max(arcs[i].j1, arcs[i].j2);
        by_pair[{a, b}].push_back(i);
    }

    struct Area {
        int j1, j2;
        int size;
        int arc_parity;
        bool odd;
    };

    vector<Area> areas;
    for(auto& [key, ids]: by_pair) {
        int len1 = arcs[ids[0]].interior_count;
        int len2 = arcs[ids[1]].interior_count;
        int sz = 2 + len1 + len2;
        Area ar;
        ar.j1 = key.first;
        ar.j2 = key.second;
        ar.size = sz;
        ar.odd = (sz % 2 == 1);
        ar.arc_parity = (len1 + 1) % 2;
        areas.push_back(ar);
    }

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

    map<int, vector<int>> jun_areas;
    for(int i = 0; i < k; i++) {
        jun_areas[areas[i].j1].push_back(i);
        jun_areas[areas[i].j2].push_back(i);
    }

    vector<int> area_order;
    area_order.reserve(k);
    int cur_area = 0;
    area_order.push_back(0);
    int next_junction = areas[0].j2;
    while((int)area_order.size() < k) {
        auto& vv = jun_areas[next_junction];
        int next_area = (vv[0] == cur_area) ? vv[1] : vv[0];
        area_order.push_back(next_area);
        int prev_j = next_junction;
        next_junction = (areas[next_area].j1 == prev_j) ? areas[next_area].j2
                                                        : areas[next_area].j1;
        cur_area = next_area;
    }

    vector<int> ordered_junctions(k);
    for(int i = 0; i < k; i++) {
        int a = area_order[i], b = area_order[(i + 1) % k];
        int sj;
        if(areas[a].j1 == areas[b].j1 || areas[a].j1 == areas[b].j2) {
            sj = areas[a].j1;
        } else {
            sj = areas[a].j2;
        }

        ordered_junctions[i] = sj;
    }

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

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

    vector<bool> remove_junction(k, false);

    if(p == 0) {
        int macro_parity = 0;
        for(int i = 0; i < k; i++) {
            macro_parity ^= areas[area_order[i]].arc_parity;
        }
        if(macro_parity != 0) {
            remove_junction[0] = true;
        }
    } else if(p == k) {
        for(int i = 0; i + 1 < k; i += 2) {
            remove_junction[i] = true;
        }
        if(k % 2 == 1) {
            remove_junction[k - 1] = true;
        }
    } else {
        int start_pos = 0;
        while(is_odd[start_pos]) {
            start_pos = (start_pos + 1) % k;
        }

        int i = 0;
        while(i < k) {
            int pos = (start_pos + i) % k;
            if(!is_odd[pos]) {
                i++;
                continue;
            }

            int run_len = 0;
            while(i + run_len < k && is_odd[(start_pos + i + run_len) % k]) {
                run_len++;
            }

            for(int j = 0; j + 1 < run_len; j += 2) {
                int p1 = (start_pos + i + j) % k;
                remove_junction[p1] = true;
            }

            if(run_len % 2 == 1) {
                int last_pos = (start_pos + i + run_len - 1) % k;
                remove_junction[last_pos] = true;
            }

            i += run_len;
        }
    }

    set<int> removed;
    for(int i = 0; i < k; i++) {
        if(remove_junction[i]) {
            removed.insert(ordered_junctions[i]);
        }
    }

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

        queue<int> q;
        q.push(s);
        color[s] = 0;
        while(!q.empty()) {
            int v = q.front();
            q.pop();
            for(int u: adj[v]) {
                if(removed.count(u)) {
                    continue;
                }
                if(color[u] == -1) {
                    color[u] = 1 - color[v];
                    q.push(u);
                }
            }
        }
    }

    vector<int> c0, c1;
    for(int v = 1; v <= n; v++) {
        if(color[v] == 0) {
            c0.push_back(v);
        } else if(color[v] == 1) {
            c1.push_back(v);
        }
    }

    cout << c0.size();
    for(int v: c0) {
        cout << ' ' << v;
    }

    cout << '\n';
    cout << c1.size();
    for(int v: c1) {
        cout << ' ' << v;
    }
    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();
        solve();
    }

    return 0;
}
```

---

5. Python implementation with detailed comments

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


def main():
    # Read all integers from input.
    data = list(map(int, sys.stdin.buffer.read().split()))

    # First two integers are n and m.
    n = data[0]
    m = data[1]

    # Build adjacency list.
    adj = [[] for _ in range(n + 1)]

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

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

    # Compute degree of each vertex.
    deg = [0] * (n + 1)
    for v in range(1, n + 1):
        deg[v] = len(adj[v])

    # arcs will store triples:
    # (junction1, junction2, number_of_internal_degree_2_vertices)
    arcs = []

    # To avoid discovering the same arc twice, remember directed first edges.
    seen_first_edge = set()

    # Start from every junction.
    for j in range(1, n + 1):
        # Junctions are exactly degree-4 vertices.
        if deg[j] != 4:
            continue

        # Each neighbor starts one possible arc.
        for x in adj[j]:
            # If this directed boundary edge was already processed, skip it.
            if (j, x) in seen_first_edge:
                continue

            # Walk from junction j through degree-2 vertices.
            interior_count = 0
            prev = j
            cur = x

            # Continue until another degree-4 junction is reached.
            while deg[cur] == 2:
                interior_count += 1

                # Move to the neighbor different from prev.
                if adj[cur][0] == prev:
                    nxt = adj[cur][1]
                else:
                    nxt = adj[cur][0]

                prev, cur = cur, nxt

            # Now cur is the other junction.
            # Mark both directions of this arc as seen.
            seen_first_edge.add((j, x))
            seen_first_edge.add((cur, prev))

            # Store the arc.
            arcs.append((j, cur, interior_count))

    # Group arcs by unordered pair of endpoint junctions.
    by_pair = defaultdict(list)

    for i, (j1, j2, cnt) in enumerate(arcs):
        a = min(j1, j2)
        b = max(j1, j2)
        by_pair[(a, b)].append(i)

    # Reconstruct all areas.
    areas = []

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

        len1 = arcs[id1][2]  # Internal vertices on first arc.
        len2 = arcs[id2][2]  # Internal vertices on second arc.

        # Area vertices are two junctions plus internal vertices of both arcs.
        size = 2 + len1 + len2

        # Edge-length parity of first arc is len1 + 1.
        arc_parity = (len1 + 1) % 2

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

    k = len(areas)

    # For every junction, store the two areas that contain it.
    jun_areas = defaultdict(list)

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

    # Order the areas around the meta-cycle.
    area_order = [0]

    cur_area = 0

    # Choose one junction of area 0 to define traversal direction.
    next_junction = areas[0]["j2"]

    # Walk through neighboring areas until all are ordered.
    while len(area_order) < k:
        shared_areas = jun_areas[next_junction]

        # Move to the other area sharing next_junction.
        if shared_areas[0] == cur_area:
            next_area = shared_areas[1]
        else:
            next_area = shared_areas[0]

        area_order.append(next_area)

        # Leave next_area through its other junction.
        prev_junction = next_junction

        if areas[next_area]["j1"] == prev_junction:
            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]

        # Find the common junction.
        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"]

    # Boolean array telling whether each ordered area is odd.
    is_odd = [False] * k

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

    # Count odd areas.
    odd_count = sum(is_odd)

    # remove_junction[i] means deleting ordered_junctions[i],
    # the junction between ordered area i and i+1.
    remove_junction = [False] * k

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

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

        # If the global cycle is odd, delete any junction.
        if macro_parity != 0:
            remove_junction[0] = True

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

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

    else:
        # There is at least one even area.
        # Start from an even area so odd areas appear as linear runs.
        start_pos = 0

        while is_odd[start_pos]:
            start_pos = (start_pos + 1) % k

        i = 0

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

            # Skip even areas.
            if not is_odd[pos]:
                i += 1
                continue

            # Measure this run of consecutive odd areas.
            run_len = 0

            while i + run_len < k:
                cur_pos = (start_pos + i + run_len) % k
                if not is_odd[cur_pos]:
                    break
                run_len += 1

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

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

                j += 2

            # If the run length is odd, cover the leftover odd area.
            if run_len % 2 == 1:
                last_pos = (start_pos + i + run_len - 1) % k
                remove_junction[last_pos] = True

            i += run_len

    # Convert selected junction positions into actual removed vertices.
    removed = set()

    for i in range(k):
        if remove_junction[i]:
            removed.add(ordered_junctions[i])

    # Bipartite-color the remaining graph.
    color = [-1] * (n + 1)

    for s in range(1, n + 1):
        # Skip deleted and already colored vertices.
        if s in removed or color[s] != -1:
            continue

        # BFS from this component.
        q = deque([s])
        color[s] = 0

        while q:
            v = q.popleft()

            for u in adj[v]:
                # Removed vertices do not exist in the remaining graph.
                if u in removed:
                    continue

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

    # Collect both color classes.
    c0 = []
    c1 = []

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

    # Print answer.
    out = []

    out.append(str(len(c0)) + (" " + " ".join(map(str, c0)) if c0 else ""))
    out.append(str(len(c1)) + (" " + " ".join(map(str, c1)) if c1 else ""))

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


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