Pls... help me out with this problem

http://www.spoj.com/problems/ANGELS/

It uses bipartite matching i guess. But am not able to build the graph .

Is there any condition for a graph to have a circuit that is both eulerian and hamiltonian ??

I came across this problem on Uva online judge from NWERC regional semilive 2010

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2946

I have thought about a method where map<vector<pair<int,int>>,int> dp stores the best possible score Jan for the state vector<pair<int,int>>.... but i dont know how to proceed further and feel that the method is inefficient...

please help......