Find maximal matching using Kuhn algo.  Then greedily add missing connections.
That is slow way.
My C++ solution without any STL use runs in 230-240 ms.

I found how to speed it up.
Just use any stupid greedy algorithm to build some initial matching.
After that apply Kuhn algo.
Running time dramatically dropped to 31 ms in my case.

Edited by author 05.06.2017 00:17