(Challenge) Building Anthills

The queen of ants hired Ada to build their anthill. Ada designed the anthill as $N$ rooms (numbered $1$ through $N$) interconnected by $M$ bidirectional roads (numbered $1$ through $M$). For simplicity, let's denote a road that connects rooms $u$ and $v$ by $(u, v)$. At any time, there may be at most one road between any two rooms and roads connecting a room with itself are not allowed. Ada sta