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

371. Subway
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



You need to create the plan of building subway in the city of S***. The subway must consist of some circle lines, each consisting of three or more stations, up to ten stations. Each circle line must be linked as a loop: first station is linked with second, second with third and so on. The circle lines themselves are linked as a chain: changing from one circle line to another is possible only at one station for each consecutive pair of circle lines in that chain. Other pairs of circle lines have no intersections. Any non-degenerate segment of subway is allowed to be contained only by one circle line.

Also it is needed to add radial lines, which start on some stations of circle lines and go to the distant parts of city. Unfortunately, due to lack of funds, radial line is allowed to consist only of two stations, one of them connects the radial line to circle line, and the other station is the terminal station. Terminal station cannot lie on more than one line. Any transfer station, which connects any two lines, could not connect more than two lines. No two radial lines are allowed to have common stations.

It is required to build exactly N stations and M segments between stations. Your task is to find the plan.

Input
First line contains two integers N and M ().

Output
First line must contain the number of circle lines K. K lines follow, each describing one circle line. Circle line is described by the number of stations on it, then the station numbers themselves in traversing order. The next line contains R — the number of radial lines. R last lines contain pairs describing radial lines. All stations are numbered from 1 to N. Your plan must consist of exactly N stations and M connecting segments. If there is no solution, output "No solution" without quotes.

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

sample input
sample output
4 3
No solution 

Picture describing the first sample

<|response|>
## 1) Abridged problem statement (concise)

Given integers **N** (stations) and **M** (segments), construct a subway network with:

- **K circle lines** (simple cycles), each of length **3..10**.
- Circle lines form a **chain**: circle *i* and *i+1* share **exactly one station** (transfer), and non-neighbors do not intersect.
- No segment belongs to more than one circle line.
- Additionally, there are **radial lines**, each a single edge connecting:
  - one station on a circle line to
  - a **unique terminal** station (degree 1) not used by any other line.
- Any transfer station can connect **at most two lines** ⇒ radials must not attach to transfer stations.

Output any valid plan using exactly **N** stations and **M** segments, or print **`No solution`**.

---

## 2) Key observations

### A) Number of circle lines is forced
For a connected graph, the cyclomatic number (#independent cycles) is:
\[
K = M - N + 1
\]
Our structure contains exactly the cycles coming from circle lines (radials add no cycles), so **K is fixed**.

If **K < 1**, there must be no cycles, but the subway requires circle lines ⇒ **impossible**.

---

### B) Let \(s\) be the sum of all cycle lengths
Each circle of length \(L\) contributes exactly \(L\) edges.

Because consecutive circles share exactly one station, total **distinct** stations used by all circles is:
\[
V_{\text{circle}} = s - (K-1)
\]

All remaining stations must be terminals of radial lines:
\[
R = N - V_{\text{circle}} = N - (s-(K-1)) = N + K - 1 - s
\]
So we need **\(R \ge 0\)** ⇒
\[
s \le N + K - 1
\]

---

### C) Radials can attach only to non-transfer circle stations
There are exactly \(K-1\) transfer stations (each shared between two circles).  
Attaching a radial to a transfer station would make it belong to **3 lines**, forbidden.

Count attachable (non-transfer) circle stations:

- circle-distinct stations: \(s-(K-1)\)
- transfer stations among them: \(K-1\)

So attachable stations:
\[
A = (s-(K-1)) - (K-1) = s - 2(K-1)
\]

We must have enough attach points for all radials:
\[
R \le A
\]
Substitute \(R = N + K - 1 - s\):
\[
N + K - 1 - s \le s - 2(K-1)
\Rightarrow s \ge \left\lceil \frac{N + 3K - 3}{2} \right\rceil
\]

---

### D) Circle size bounds
Each circle has length 3..10:
\[
3K \le s \le 10K
\]

---

### E) Feasibility reduces to existence of integer \(s\)
We need an integer \(s\) such that:
\[
s \in \Big[\max\left(3K,\left\lceil\frac{N+3K-3}{2}\right\rceil\right),\ \min(10K, N+K-1)\Big]
\]
If the interval is empty ⇒ **No solution**.

---

## 3) Full solution approach

1. Read **N, M**.
2. Compute **K = M − N + 1**.
   - If **K < 1** ⇒ print `No solution`.
3. Compute bounds for total cycle length sum \(s\):
   - \[
     s_{\min}=\max\left(3K,\left\lceil\frac{N+3K-3}{2}\right\rceil\right)
     \]
     Implement ceiling as:
     \[
     \left\lceil\frac{x}{2}\right\rceil = \frac{x+1}{2} \text{ (integer division)}
     \]
     Here \(x=N+3K-3\) ⇒ \(\lceil(N+3K-3)/2\rceil = (N+3K-2)/2\).
   - \[
     s_{\max}=\min(10K, N+K-1)
     \]
   - If \(s_{\min}>s_{\max}\) ⇒ `No solution`.
4. Choose \(s=s_{\min}\) (any value in range works).
5. Choose individual cycle sizes:
   - Start all **K** cycles with size 3.
   - Distribute `extra = s - 3K` among cycles, adding at most 7 to each (to not exceed 10).
6. Construct the chain of cycles with station IDs:
   - Maintain `prev_shared` transfer station (initially none).
   - For each circle:
     - If not first: start with `prev_shared` as first station.
     - Add fresh station IDs until circle reaches its intended size.
     - If not last: set `prev_shared` = last station (shared with next circle).
7. Collect all **non-transfer** circle stations as possible radial attachment points:
   - In circle i:
     - first station is transfer if i>0
     - last station is transfer if i<K-1
8. Every station ID not used yet (from `next_id` to N) is a radial terminal.
   - Connect each terminal to the next available attach point.
9. Output circles then radials.

Complexity is **O(N)** time and space.

---

## 4) C++ implementation (detailed comments)

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

/*
  Constructive solution for Timus/ACM-like problem "Subway" (p371).

  We compute K = M - N + 1. Then find feasible total sum of cycle lengths s.
  Build K cycles in a chain sharing exactly one station between neighbors.
  Attach remaining stations as 2-vertex radial lines to non-transfer stations.
*/

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

    int N, M;
    cin >> N >> M;

    // Number of circle lines (cycles) is forced by cyclomatic number:
    // K = E - V + 1 for connected graph.
    int K = M - N + 1;
    if (K < 1) {
        cout << "No solution\n";
        return 0;
    }

    // Lower bound:
    // 1) each cycle has at least 3 vertices => s >= 3K
    // 2) need enough non-transfer stations to attach all radials:
    //    s >= ceil((N + 3K - 3)/2)
    int s_min = max(3 * K, (N + 3 * K - 2) / 2); // ceil via (x+1)/2

    // Upper bound:
    // 1) each cycle has at most 10 vertices => s <= 10K
    // 2) number of radials R = N + K - 1 - s must be >= 0 => s <= N + K - 1
    int s_max = min(10 * K, N + K - 1);

    if (s_min > s_max) {
        cout << "No solution\n";
        return 0;
    }

    // Pick any feasible s; simplest is minimal one.
    int s = s_min;

    // Decide each cycle size: start with 3 and distribute extra up to 10.
    vector<int> sizes(K, 3);
    int extra = s - 3 * K;
    for (int i = 0; i < K && extra > 0; i++) {
        int add = min(extra, 7); // 3 + 7 = 10 max
        sizes[i] += add;
        extra -= add;
    }

    // Build the cycles with actual station labels.
    vector<vector<int>> circles(K);

    int next_id = 1;       // next fresh station number to allocate
    int prev_shared = -1;  // station shared with previous circle (transfer)

    for (int i = 0; i < K; i++) {
        auto &c = circles[i];

        // Chain rule: circle i and i-1 share exactly one station.
        // We implement by reusing prev_shared as first station (except first circle).
        if (prev_shared != -1) c.push_back(prev_shared);

        // Fill remaining positions with new station ids.
        while ((int)c.size() < sizes[i]) {
            c.push_back(next_id++);
        }

        // For all but last circle, last station becomes shared with next circle.
        if (i + 1 < K) prev_shared = c.back();
    }

    // Collect all non-transfer stations to attach radials.
    // Transfer stations are:
    // - first station of circle i if i > 0 (shared with previous)
    // - last station of circle i if i < K-1 (shared with next)
    vector<int> attach;
    attach.reserve(N);

    for (int i = 0; i < K; i++) {
        int L = sizes[i];
        for (int j = 0; j < L; j++) {
            bool is_transfer =
                (i > 0 && j == 0) ||         // shared with previous
                (i + 1 < K && j == L - 1);   // shared with next

            if (!is_transfer) attach.push_back(circles[i][j]);
        }
    }

    // Remaining station IDs are radial terminals.
    // Each terminal connects to one attach point; terminals are unique by construction.
    vector<pair<int,int>> radials;
    int idx = 0;
    for (int t = next_id; t <= N; t++) {
        // Feasibility guarantees idx < attach.size()
        radials.push_back({attach[idx++], t});
    }

    // Output format:
    // K
    // K lines: size followed by the stations in traversal order
    // R
    // R lines: u v for each radial edge
    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 [u, v] : radials) {
        cout << u << ' ' << v << "\n";
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

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

    # Forced number of circle lines by cycle rank:
    K = M - N + 1
    if K < 1:
        print("No solution")
        return

    # Feasible total sum of cycle lengths s:
    # s >= 3K
    # s >= ceil((N + 3K - 3)/2)  -> computed as (N + 3K - 2)//2
    s_min = max(3 * K, (N + 3 * K - 2) // 2)

    # s <= 10K
    # s <= N + K - 1  (so radials R = N + K - 1 - s is non-negative)
    s_max = min(10 * K, N + K - 1)

    if s_min > s_max:
        print("No solution")
        return

    s = s_min

    # Decide sizes of individual circles: start at 3 and distribute extra, max 10.
    sizes = [3] * K
    extra = s - 3 * K
    for i in range(K):
        if extra <= 0:
            break
        add = min(extra, 7)  # cannot exceed size 10
        sizes[i] += add
        extra -= add

    # Build circles as a chain sharing exactly one station between neighbors.
    circles = [[] for _ in range(K)]
    next_id = 1
    prev_shared = None

    for i in range(K):
        c = circles[i]
        if prev_shared is not None:
            c.append(prev_shared)

        while len(c) < sizes[i]:
            c.append(next_id)
            next_id += 1

        if i + 1 < K:
            prev_shared = c[-1]

    # Collect non-transfer stations as radial attachment points.
    attach = []
    for i in range(K):
        L = sizes[i]
        for j in range(L):
            is_transfer = (i > 0 and j == 0) or (i + 1 < K and j == L - 1)
            if not is_transfer:
                attach.append(circles[i][j])

    # Remaining stations become terminals of radials.
    radials = []
    idx = 0
    for t in range(next_id, N + 1):
        radials.append((attach[idx], t))
        idx += 1

    # Output
    out = []
    out.append(str(K))
    for i in range(K):
        out.append(str(sizes[i]) + " " + " ".join(map(str, circles[i])))
    out.append(str(len(radials)))
    out.extend(f"{u} {v}" for u, v in radials)

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

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

