Lexicographic Rook on a Graph

A rook placed on an undirected graph behaves slightly differently than a rook placed on a chessboard. You are given an undirected, connected graph with $N$ nodes and $M$ edges. In one move, a rook placed on node $U$ can: - Choose an integer $d$, such that $1 \leq d \leq degree(U)$. Note that $degree(U)$ denotes the number of edges connected to node $U$. - Move to the $d^{th}$ **lexicographicall