Since compressing the blocks of cycles into single nodes gives a tree, we can actually use the same method of finding the longest path in a tree to get the longest shortest path of this graph: Start BFS from any node, then do another BFS from the farthest node found in the first BFS. You may do this on the original graph without compressing anything, as the shortest path will always be equal to the Manhattan distance between the ends of the block.

To avoid changing the row in the middle of a block of cycles, we want our path to change its row at the first column of the block, if needed.

To do that, we will just sort the nodes in each adjacency list by their degrees. This way the same BFS we implemented will prefer the boundary paths.

You will see why this is useful in the next step of the solution.

We will start placing the nodes from left to right, starting at the first row. For every three consecutive nodes on the path: $$$i-1$$$, $$$i$$$, and $$$i+1$$$, if nodes $$$i-1$$$ and $$$i+1$$$ have a common adjacent node other than $$$i$$$, it means we should change the row of node $$$i$$$ (go down instead of go right, then place $$$i$$$).

This works because we have a boundary path.

For each column from left to right, if there's one filled cell, and that cell has an adjacent node that is not placed yet, place it in the empty cell of the same column.

Now we have a solution, it's only problem is that it is stretched and may not fit inside our grid of $$$c$$$ columns.

Start from the first column that has two rows filled, then every time we have 4 consecutive columns with one filled cell, we alternate the row of the second last node to the end, and set the count to 1.

####.###...
##.###.####

Note that at the end, if the counter is more than 2, move the last placed node to the previous column and change its row.

Now do the same for the prefix (before the column we started from), going from right to left.

Make sure to handle the case when there are no cycles properly.