In fact, this problem is easy, don't be frighten by the low AC ratio...

When I read the description of this problem, I immediately thought it as a Euler Path problem.

I try to add some edges so that will form a Euler Path.

First, I add edges according to greedy strategy,but soon I learnt it was wrong, a simple calc proved it won't work.

As far as I know, there isn't exist a greedy algo...
(It you used it got AC, email me: yyming@hotmail.com )

In spite of this, my pro runs quickly, it got AC in 0.015 sec :)
http://acm.timus.ru/status.aspx?space=1&pos=865497

The algo is greedy once you connect all components