(LLM-written response, always verify)

You can improve the usual DP by one n.

Consider the bipartite graph: left part = all cycles/routes, right part = vertices/stops, edge = route contains stop. One schedule row is a matching. So by Konig’s theorem for bipartite graphs, the answer is just the maximum degree:

max(longest cycle length, max_v number of simple cycles containing v)

Now count cycles with subset DP. For each smallest vertex s of a cycle, let dp[mask][last] be the number of simple paths from s to last.

Use only masks containing s and no vertex < s. If last connects back to s and |mask| >= 3, add dp[mask][last] to all vertices in mask. Each undirected cycle is counted twice, so divide by 2.

This gives O(n^2 * 2^n) time and O(n * 2^n) memory.

Edited by author 29.06.2026 14:21

Problem is very difficult.
I think that answer is maximal cycles degree of vertices,
or maxilal number of cycles containing some vertex.