P6066 [USACO05JAN] Watchcow S

Farmer John has $N$ farms ($2 \leq N \leq 10^4$). These farms are connected by $M$ roads ($1 \leq M \leq 5 \times 10^4$). Multiple edges may exist. Bessie starts patrolling from farm $1$. Each road must be traversed **exactly once in each direction**, and finally she must return to farm $1$. Please output one path that satisfies the requirements above. It is guaranteed that such a path exists. If there are multiple valid paths, output any one of them.

The first line contains two integers $N, M$. The next $M$ lines each contain two integers $u, v$, describing a road between $u$ and $v$.

Output the farms visited, one per line.

Translated by ChatGPT 5