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

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

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

- **K circle lines** (simple cycles), each of length **3..10**, chained so consecutive circles share exactly one station.
- **R radial lines**, each a single edge from a circle station to a unique terminal (degree-1) station, where radials cannot share stations with each other or attach to transfer stations.

Use stations **1..N** with exactly **M** edges, or output `No solution`.

---

## 2. Key observations

1. **K is fixed by Euler's formula.** The graph is connected with N nodes and M edges, so cycle rank = M − N + 1, giving **K = M − N + 1**. If K < 1 ⇒ impossible.

2. **Sum of circle sizes s determines radials.** With K circles chained (each adjacent pair shares 1 station), distinct circle stations = s − (K−1), leaving R = N + K − 1 − s radial terminals.

3. **Feasibility bounds on s:**
   - R ≥ 0 ⇒ s ≤ N + K − 1.
   - Each radial needs an attach point not on a transfer station; non-transfer circle count = s − 2(K−1) ≥ R, giving s ≥ ⌈(N + 3K − 3)/2⌉.
   - 3K ≤ s ≤ 10K (circle size limits).

4. A solution exists iff `s_min ≤ s_max` where `s_min = max(3K, ⌈(N+3K−3)/2⌉)` and `s_max = min(10K, N+K−1)`.

---

## 3. Full solution approach

Compute K = M − N + 1. Check K ≥ 1. Compute s_min, s_max. If s_min > s_max, output `No solution`. Otherwise pick s = s_min, start with K circles of size 3, distribute extra = s − 3K stations across circles (up to 7 extra per circle). Assign station IDs sequentially while building the chain (adjacent circles share one station). Collect non-transfer stations as attach points. Remaining IDs become radial terminals.

---

## 4. 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;
}
```

---

## 5. 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()
```
