I just want to make public my fascination towards this problem and recommend a tutorial to all the users. I loved solving this problem. It's a truly beautiful Eulerian Path problem in disguise.
It also helped me refresh my knowledge on the algorithm. I learned Eulerian Paths/Tours like 10 years ago when I first started at the USACO Gateway and then I rarely ever used it again. Now I googled it to refresh my memory, but I couldn't come upon any good implementations out there. There are a few, but all of them seem either overly complicated or inefficient. No other algorithm I found out there beats the beautiful recursive algorithm presented at the USACO Gateway.
For those not registered at USACO, you can view the tutorial here: Eulerian Paths/Tours Tutorial
A question: would you be able to solve the problem during the contest without the knowledge of Eulerian Paths ?
I certainly don't know if there's another solution to the problem...
But if you can come up with the idea of Eulerian Path during the contest all by yourself without knowing it beforehand, then yes, you could solve it.