Python3, O(n^3):

import collections, copy def cycles(n): q, q1 = collections.deque([([], [0 for _ in range(n)], 0, {}, {*range(n)}, collections.defaultdict(set))]), collections.deque() while q: result, a, s, d, ac, cache = q.popleft() if not ac: yield a, cache continue for i, x in enumerate(a): if (s or i) and (i not in d and s not in cache[i]): l, _cache = copy.deepcopy(a), copy.deepcopy(cache) _d = copy.deepcopy(d) l[i] = s _d[i] = s _cache[i].add(s) q.append((result, l, i, _d, ac-{s}, _cache)) def main(n, m): q = collections.deque([([], {}, [*cycles(n)])]) while q: result, cache, cycle = q.popleft() if len(result) == m:yield result; continue for i, (a, _cache) in enumerate(cycle): if all(not cache.get(j, set())&_cache[j] for j in _cache): q.appendleft((result + [a], {j:cache.get(j, set())|_cache[j] for j in _cache}, cycle[:i]+cycle[i+1:])) 

Try it online!

Generates all possible deranged cycles for a given m and n.