This is a challenge that was originally a tas for the German Bundeswettbewerb Informatik (federal competition of computer science [?]), a competition for highschool students. As opposed to the original question, where you have to find a good solution and write some documentation, I want you to golf this. I try to replicate the question as good as possible:
Challenge
Many towns in Europe have so-called twin towns. This year, there is a special Jubilee where each pair of twin-towns in the EU organizes a festival to celebrate their partnership. To ensure that no city has to organize too many festivals, each city has a limit of festivals it can organize. Is it possible to distribute the festivals among the twin-towns in a way, such that each pair of twin-towns organizes one festival in one the two towns and no town organizes more festivals than it is allowed to? If yes, explain how.
This is a map of some towns, their partnerships and their limits of festivals.
Requirements
Your program must terminate the problem in one minute each for both testcases. (See below)
Refer to the testcases for the input format.
The output should be empty iff no solution exists and should have the following format otherwise: One line for each pair of twin towns,
a
ifcity1
organizes the festival,b
otherwise.<city1>, <city2>, <a/b>
The solution with the least number of characters that satisfies the requirements wins. In case of a tie, the program that was submitted first wins.
Usual code-golf rules apply.
Testcases
The original task had two testcases. I have uploaded them on github.
n
nodes, wheren
is the budget limit of the city). \$\endgroup\$