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

236. Greedy Path
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



There are N towns and M routes between them. Recently, some new travel agency was founded for servicing tourists in these cities. We know cost which tourist has to pay, when traveling from town i to town j which equals to Cij and time needed for this travel - Tij. There are many tourists who want to use this agency because of very low rates for travels, but agency still has only one bus. Head of agency decided to organize one big travel route to gain maximal possible amount of money. Scientists of the company offer to find such a cyclic path G, when greedy function f(G) will be maximum. Greedy function for some path is calculated as total cost of the path (sum of Cij for all (i,j) - routes used in path) divided by total time of path (similar to Cij). But nobody can find this path, and Head of the company asks you to help him in solving this problem.

Input
There are two integers N and M on the first line of input file (3<=N<=50). Next M lines contain routes information, one route per line. Every route description has format A, B, Cab, Tab, where A is starting town for route, B - ending town for route, Cab - cost of route and Tab - time of route (1<=Cab<=100; 1<=Tab<=100; A<>B). Note that order of towns in route is significant - route (i,j) is not equal to route (j,i). There is at most one route (in one direction) between any two towns.

Output
You must output requested path G in the following format. On the first line of output file you must output K - number of towns in the path (2<=K<=50), on the second line - numbers of these towns in order of passing them. If there are many such ways - output any one of them, if there are no such ways - output "0" (without quotes).

Sample test(s)

Input
4 5
1 2 5 1
2 3 3 5
3 4 1 1
4 1 5 2
2 4 1 10

Output
4
1 2 3 4
Author: Sergey Simonchik
Resource:   ---
Date:   December, 2003

<|response|>
1. Abridged Problem Statement  
Given a directed graph with N towns and M one-way routes. Each route (u→v) has a cost C and a travel time T. Find a simple directed cycle (length ≥2) that maximizes the ratio  
    (sum of costs on the cycle) / (sum of times on the cycle).  
If no cycle exists, output 0. Otherwise, output the number of vertices in the cycle followed by the sequence of towns in order.

2. Key Observations  
- Maximizing (ΣC)/(ΣT) over cycles is the classic maximum mean weight cycle problem.  
- For any real λ, a cycle has mean cost/time > λ exactly when  
    Σ(C − λT) > 0  
  on that cycle.  
- Equivalently, if we define modified weight w′(e) = λ·T(e) − C(e), then a cycle with Σw′ < 0 corresponds to a cycle with mean cost/time > λ.  
- We can binary-search λ over a suitable interval (e.g. [0, 200]) to find the maximum ratio.  
- To test for a negative cycle in w′, run Bellman-Ford on the graph (plus a super-source connected to all nodes with zero-weight edges) and check for distance relaxations in the Nth iteration.

3. Full Solution Approach  
1. Read N, M and the edge list (u, v, C, T).  
2. Set lower and upper bounds for λ: lo = 0.0, hi = max_possible_ratio (e.g. 200.0 since C≤100, T≥1).  
3. Repeat ~80–100 iterations:  
   a. mid = (lo + hi)/2.  
   b. For each edge e, compute modified weight w′(e) = mid·T(e) − C(e).  
   c. Run Bellman-Ford with N+1 nodes: nodes 1..N plus a super-source S.  
      - Initialize dist[S] = 0, dist[v] = +∞ for v=1..N.  
      - In each of N rounds, relax all edges (u→v) with weight w′, and relax S→v edges with weight 0.  
   d. After N rounds, do one more pass over all edges to see if any dist[v] can still be lowered.  
      - If yes, a negative cycle exists in w′, meaning there is a cycle with mean cost/time > mid, so set lo = mid.  
      - Otherwise, set hi = mid.  
4. After binary search, λ≈lo is the maximum ratio. Run one final Bellman-Ford at x = lo, detect a negative cycle, and reconstruct it:  
   a. When you find a vertex v that still relaxes, walk back N steps via parent pointers to ensure you enter the cycle.  
   b. From that node, follow parent pointers until you return to it, collecting the cycle vertices. Reverse them to get the order of traversal.  
5. If no cycle was ever found, output 0. Otherwise, output the cycle length and sequence.

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

struct Edge {
    int u, v, c, t;
};

int n, m;
vector<Edge> edges;
vector<double> dist;
vector<int> par;

void read() {
    cin >> n >> m;
    edges.resize(m);
    for(int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].c >> edges[i].t;
    }
}

pair<bool, vector<int>> check(double x) {
    dist.assign(n + 2, 1e18);
    par.assign(n + 2, -1);

    int source = n + 1;
    dist[source] = 0;

    for(int i = 0; i < n; i++) {
        for(auto& e: edges) {
            double weight = e.t * x - e.c;
            if(dist[e.u] < 1e17 && dist[e.u] + weight < dist[e.v]) {
                dist[e.v] = dist[e.u] + weight;
                par[e.v] = e.u;
            }
        }

        for(int v = 1; v <= n; v++) {
            if(dist[source] < dist[v]) {
                dist[v] = dist[source];
                par[v] = source;
            }
        }
    }

    int cycle_node = -1;
    for(auto& e: edges) {
        double weight = e.t * x - e.c;
        if(dist[e.u] < 1e17 && dist[e.u] + weight < dist[e.v]) {
            cycle_node = e.v;
            break;
        }
    }

    if(cycle_node == -1) {
        return {false, {}};
    }

    for(int i = 0; i < n; i++) {
        cycle_node = par[cycle_node];
    }

    vector<int> cycle;
    int curr = cycle_node;
    do {
        cycle.push_back(curr);
        curr = par[curr];
    } while(curr != cycle_node);

    reverse(cycle.begin(), cycle.end());
    return {true, cycle};
}

void solve() {
    // We maximize the cycle ratio (sum of costs) / (sum of times). Binary search
    // the answer x: a cycle with ratio > x exists iff some cycle has positive
    // sum of (c - t*x), equivalently a negative cycle under edge weight
    // t*x - c. We detect such a cycle with N relaxation rounds of Bellman-Ford
    // from a virtual super-source connected to every node, then one extra round
    // to find an edge that still relaxes; walking N parent steps lands inside the
    // negative cycle, which we trace via the parent array and report.

    double l = 0.0, r = 200.0;
    for(int i = 0; i < 100; i++) {
        double mid = (l + r) / 2;
        auto [has_cycle, cycle] = check(mid);
        if(has_cycle) {
            l = mid;
        } else {
            r = mid;
        }
    }

    auto [has_cycle, cycle] = check(l);
    if(!has_cycle) {
        cout << "0\n";
        return;
    }

    cout << cycle.size() << "\n";
    cout << cycle << "\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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments

import sys
sys.setrecursionlimit(10**7)

def read_ints():
    return map(int, sys.stdin.readline().split())

def find_negative_cycle(n, edges, x):
    """
    Detects a negative cycle under weights w = x*t - c using Bellman-Ford.
    Returns (found_cycle, list_of_vertices_in_cycle).
    """
    INF = float('inf')
    # We use 1..n for real nodes, n+1 as super-source
    S = n + 1
    dist = [INF] * (n + 2)
    parent = [-1]  * (n + 2)
    dist[S] = 0.0

    # Relax edges n times
    for _ in range(n):
        # Relax real edges
        for u, v, c, t in edges:
            w = x * t - c
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
        # Relax super-source → every node
        for v in range(1, n + 1):
            if dist[S] < dist[v]:
                dist[v] = dist[S]
                parent[v] = S

    # One more pass to find a cycle
    cycle_start = -1
    for u, v, c, t in edges:
        w = x * t - c
        if dist[u] + w < dist[v]:
            cycle_start = v
            break

    if cycle_start == -1:
        return False, []

    # Walk back n steps to enter the cycle
    v = cycle_start
    for _ in range(n):
        v = parent[v]

    # Reconstruct cycle
    cycle = []
    curr = v
    while True:
        cycle.append(curr)
        curr = parent[curr]
        if curr == v:
            break
    cycle.reverse()
    return True, cycle

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n, m = int(next(it)), int(next(it))
    edges = []
    for _ in range(m):
        u = int(next(it))
        v = int(next(it))
        c = int(next(it))
        t = int(next(it))
        edges.append((u, v, c, t))

    # Binary search for best λ in [0, 200]
    lo, hi = 0.0, 200.0
    for _ in range(80):
        mid = (lo + hi) / 2.0
        found, _ = find_negative_cycle(n, edges, mid)
        if found:
            lo = mid
        else:
            hi = mid

    # Recover the cycle at λ = lo
    found, cycle = find_negative_cycle(n, edges, lo)
    if not found:
        print(0)
    else:
        print(len(cycle))
        print(" ".join(map(str, cycle)))

if __name__ == "__main__":
    main()

Explanation Summary  
- We binary-search the maximum possible average cost/time ratio λ.  
- For each candidate λ, we transform edge weights and detect a negative cycle via Bellman-Ford (with a super-source for disconnected parts).  
- Once we pinpoint λ to sufficient precision, we rerun the detection to reconstruct and output one optimal cycle.