AFAIK that one is same with problem KAMPANJA.

Solution link.

You can model the problem into a bitonic tour instance, and run a shortest path algorithm on the state graph. Time complexity is about O(n³) ~ O(n⁴).

I have tried to get the problem accepted most of the day. But I can not get it correct. I have written different solutions, but they all the same wrong result. I have tried writing with and without a blank line after each test case. I have also tried writing "Impossible" instead of "IMPOSSIBLE" because that is what the solution on uDebug does. Any help is appreciated.

Here is my python solution, which gets TLE(the TLE is not the problem, because it gets the same result as the c++ solution): https://pastebin.com/gJB8a2v2

This is my brute force: https://pastebin.com/ZdavPK4M

I use this script to generate data: https://pastebin.com/bYYryFAb

This is a modification of the c++ solution ko_osaga posted: https://pastebin.com/D5U83tdm

I have tried submitting here: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=35&page=show_problem&category=0&problem=3498&mosmsg=Submission+received+with+ID+23069820

and here: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1571&mosmsg=Submission+received+with+ID+2527676

I have tried testing my solution here: https://www.udebug.com/LA/3570 and here https://www.udebug.com/UVa/1057