## 1. Abridged problem statement

Given integers **N** (stations) and **M** (segments), construct a subway plan consisting of:

- **K circle lines** (simple cycles) arranged in a **chain**:
  - Each circle has **3 to 10** stations.
  - Each consecutive pair of circles shares **exactly one station** (a transfer station).
  - Non-consecutive circles **do not intersect**.
  - No segment (edge) belongs to more than one circle.
- **R radial lines**, each being a single segment connecting:
  - one station on some circle to
  - a unique terminal station not used anywhere else.
  - Radials are disjoint (no shared stations), and terminals are degree 1.
- Any transfer station connects **at most two lines**.

Use station labels **1..N**. Output any valid construction with exactly **N stations** and **M segments**, or output **`No solution`**.

---

## 2. Detailed editorial

### Key counting observation: number of circles is fixed

The subway graph described is connected and "planar-like" with a very specific structure (chain of cycles + leaf radials). The intended invariant used in the code is:

- Let **K** be the number of circle lines.
- Then necessarily \(K = M - N + 1\).

If \(K < 1\), you cannot have any circle line ⇒ impossible.

(The graph is connected with M edges and N nodes: the cyclomatic number = M − N + 1 counts the number of independent cycles.)

So we can compute **K** immediately.

---

### Let \(s\) be the sum of circle sizes

Let \(s\) be the total number of station occurrences across all circles (sum of lengths of each cycle).

Because circles form a chain, each adjacent pair shares exactly one station, so the number of **distinct stations used by the circles** is:
\[
V_{\text{circle}} = s - (K-1)
\]

Hence the number of stations left for radial terminals is:
\[
N - V_{\text{circle}} = N - (s-(K-1)) = N + K - 1 - s
\]

Each radial consumes exactly 1 of these leftover stations (a terminal) and uses 1 edge.

So:
- Number of radials is forced to be \(R = N + K - 1 - s\).
- And total edges = circle edges + radial edges = \(s + R = N + K - 1 = M\). This is consistent with K = M − N + 1.

Thus once K is fixed, we only need to find a feasible \(s\) and actual circle sizes.

---

### Radials can only attach to non-transfer circle stations

In the chain of circles, there are exactly \(K-1\) shared (transfer) stations between consecutive circles. Attaching a radial to a transfer station would give it three lines, which is forbidden.

The number of **non-transfer circle stations** available to attach radials equals:
\[
A = V_{\text{circle}} - (K-1) = (s-(K-1))-(K-1) = s-2(K-1)
\]

We must have \(R \le A\), i.e., \(N + K - 1 - s \le s - 2(K-1)\), which gives:
\[
s \ge \left\lceil\frac{N + 3K - 3}{2}\right\rceil
\]

Also, radials count must be non-negative (\(R \ge 0\)):
\[
s \le N + K - 1
\]

And circle size constraints:
\[
3K \le s \le 10K
\]

So a solution exists iff there is an integer \(s\) such that:
\[
s \in \Big[ \max(3K, \lceil\frac{N+3K-3}{2}\rceil),\ \min(10K, N+K-1)\Big]
\]

The code computes:
- `s_min = max(3*k, (n + 3*k - 2)/2)` (the ceiling via integer division)
- `s_max = min(10*k, n + k - 1)`

and checks `s_min <= s_max`.

---

### Constructing the circles

Once a feasible `s` is chosen (the code picks `s = s_min`):
- Start with all sizes = 3 (minimum).
- Distribute `extra = s - 3K` across circles, adding at most 7 to any circle (since max size 10).

Then assign station IDs:
- Walk circles from 0..K-1.
- Each circle starts with the previous shared station (except the first).
- Fill remaining positions with fresh station numbers.
- The last station of circle i becomes the shared station with circle i+1.

---

### Constructing the radials

All stations not yet used (from `next_id` up to `N`) become radial terminals. For each terminal, connect it to an available **attach** station (non-transfer circle station collected earlier).

Because we enforced `R <= A`, we have enough attach points.

---

### Complexity

All operations are linear in N.

---

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

int n, m;

void read() { cin >> n >> m; }

void solve() {
    // The first observation is that given n and m, we already know the number
    // of circle lines. To formalize this, we can notice that the graph is
    // planar and connected. Using Euler's theorem we know that |V| - |E| + |F|
    // = 2, or n - m + k = 1, where k is the number of cycles. Now the problem
    // is slightly different as we can start with having c cycles with 3
    // vertices each, and we need to figure out if we could allocate the rest of
    // the vertices. The main constraint is that each of the cycles can be at
    // most 10 vertices, but we can use the heuristic where we first try
    // expanding the 3 vertex cycles, and then try to append the rest of the
    // vertices as radial lines. If we either don't have enough vertices to
    // build the initial 3-sized cycles or we are left with some vertices after
    // expanding them and building the radial lines it's impossible. If we try
    // to make a more direct way of checking if there is a solution, we can
    // derive it as follows. By Euler's formula the number of circles must be
    // k = m - n + 1. Let s denote the total sum of circle sizes. Since
    // consecutive circles share one station, the circles together occupy
    // s - (k - 1) distinct stations. Exactly k - 1 of those are transfer
    // stations, so s - (k - 1) - (k - 1) = s - 2(k - 1) non-transfer circle
    // stations remain available to host radial terminals. Each radial
    // contributes one edge and one terminal station, so the number of radials
    // is fixed at n - (s - (k - 1)) = n + k - 1 - s, which must be non-negative
    // and at most s - 2(k - 1). The first constraint gives the upper bound s <=
    // n + k - 1, and the second rearranges to s >= ceil((n + 3k - 3) / 2). On
    // top of that, every circle has between 3 and 10 stations, which forces 3k
    // <= s <= 10k. Putting everything together, a valid s exists if and only if
    // it lies in [max(3k, ceil((n + 3k - 3) / 2)), min(10k, n + k - 1)].

    int k = m - n + 1;
    if(k < 1) {
        cout << "No solution\n";
        return;
    }

    int s_min = max(3 * k, (n + 3 * k - 2) / 2);
    int s_max = min(10 * k, n + k - 1);
    if(s_min > s_max) {
        cout << "No solution\n";
        return;
    }

    int s = s_min;
    vector<int> sizes(k, 3);
    int extra = s - 3 * k;
    for(int i = 0; i < k && extra > 0; i++) {
        int add = min(extra, 7);
        sizes[i] += add;
        extra -= add;
    }

    vector<vector<int>> circles(k);
    int next_id = 1;
    int prev_shared = -1;
    for(int i = 0; i < k; i++) {
        auto& c = circles[i];
        if(prev_shared != -1) {
            c.push_back(prev_shared);
        }
        while((int)c.size() < sizes[i]) {
            c.push_back(next_id++);
        }
        if(i + 1 < k) {
            prev_shared = c.back();
        }
    }

    vector<int> attach;
    for(int i = 0; i < k; i++) {
        int sz = sizes[i];
        for(int j = 0; j < sz; j++) {
            bool is_transfer = (i > 0 && j == 0) || (i + 1 < k && j == sz - 1);
            if(!is_transfer) {
                attach.push_back(circles[i][j]);
            }
        }
    }

    vector<pair<int, int>> radials;
    for(int t = next_id, idx = 0; t <= n; t++, idx++) {
        radials.emplace_back(attach[idx], t);
    }

    cout << k << '\n';
    for(int i = 0; i < k; i++) {
        cout << sizes[i];
        for(int x: circles[i]) {
            cout << ' ' << x;
        }
        cout << '\n';
    }
    cout << radials.size() << '\n';
    for(auto [a, b]: radials) {
        cout << a << ' ' << b << '\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;
}
```

---

## 4. Python Solution

```python
import sys

def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n = int(data[0])
    m = int(data[1])

    # Number of circle lines is fixed by cycle rank:
    k = m - n + 1
    if k < 1:
        sys.stdout.write("No solution\n")
        return

    # s must satisfy:
    # 3k <= s <= 10k
    # ceil((n + 3k - 3)/2) <= s <= n + k - 1
    s_min = max(3 * k, (n + 3 * k - 2) // 2)   # ceil((x)/2) with x = n+3k-3
    s_max = min(10 * k, n + k - 1)

    if s_min > s_max:
        sys.stdout.write("No solution\n")
        return

    s = s_min

    # Decide individual circle sizes: start at 3 and distribute extra up to 10.
    sizes = [3] * k
    extra = s - 3 * k
    i = 0
    while i < k and extra > 0:
        add = min(extra, 7)   # 3 + 7 = 10 max
        sizes[i] += add
        extra -= add
        i += 1

    # Build circles with station IDs:
    circles = [[] for _ in range(k)]
    next_id = 1
    prev_shared = None  # transfer station from previous circle (if any)

    for i in range(k):
        c = circles[i]

        # Reuse previous shared station as the first station of this circle
        if prev_shared is not None:
            c.append(prev_shared)

        # Fill remaining positions with fresh station numbers
        while len(c) < sizes[i]:
            c.append(next_id)
            next_id += 1

        # The last station becomes shared with the next circle (if any)
        if i + 1 < k:
            prev_shared = c[-1]

    # Collect all non-transfer stations as possible radial attachment points.
    attach = []
    for i in range(k):
        sz = sizes[i]
        for j in range(sz):
            # Transfer if it's shared with previous (first) or next (last)
            is_transfer = (i > 0 and j == 0) or (i + 1 < k and j == sz - 1)
            if not is_transfer:
                attach.append(circles[i][j])

    # Remaining station IDs [next_id..n] are radial terminals.
    radials = []
    idx = 0
    for t in range(next_id, n + 1):
        # Connect attach[idx] -- t
        radials.append((attach[idx], t))
        idx += 1

    # Output in required format
    out_lines = []
    out_lines.append(str(k))
    for i in range(k):
        out_lines.append(str(sizes[i]) + " " + " ".join(map(str, circles[i])))
    out_lines.append(str(len(radials)))
    out_lines.extend(f"{a} {b}" for a, b in radials)

    sys.stdout.write("\n".join(out_lines) + "\n")


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

---

## 5. Compressed editorial

Compute **K = M − N + 1**. If **K < 1** ⇒ `No solution`. Let **s** be the sum of cycle lengths. Circles use **s − (K−1)** distinct stations (adjacent circles share 1 station). Radials count is forced: **R = N + K − 1 − s**, so we need **s ≤ N + K − 1**. Radials must attach to non-transfer circle stations. Non-transfer count is **A = s − 2(K−1)**, so require **R ≤ A**, yielding \(s \ge \lceil(N + 3K - 3)/2\rceil\). Also each circle has 3..10 stations ⇒ **3K ≤ s ≤ 10K**. Feasible iff \(s \in [\max(3K, \lceil(N+3K-3)/2\rceil),\ \min(10K, N+K-1)]\) is non-empty. Construct cycles: start with size 3 each, distribute extra up to 10; chain them by sharing the last vertex of circle i with first of circle i+1. Attach remaining stations as 2-vertex radials to non-transfer circle stations.
