[mappu]

Came to the same realisation - it's a vertex cycle cover, which can be found in polynomial time! (if one exists)

https://en.wikipedia.org/wiki/Vertex_cycle_cover