I solved it with next algo:
I bruteforce all possible connections (if graph consists of several not connected parts) and then add some edges for Euler path with greedy.

Of course its right algo, but some complicated (i think).
Does anyone knows more simple one?