Directions#406
In Tenture, not everyone is privileged enough to wear crimson pants, and very few own a pepelats with a gravitsapa, making interplanetary travel a challenge for most residents. However, a resourceful Chatlanian from the planet Pluk has recently entered the passenger transport market, offering travel between planets for a few chatls. The journey begins and ends on the planet Pluk, with several other planets visited in between.
The first line of input contains the number of test cases. For each test case, the first line contains (N \leq 22) — the number of planets served by the route (not counting Pluk). The next lines contain information about each planet in the following format: planet type (Latin uppercase letter for Chatlanian, for Patsak), the number of Chatlanians traveling to this planet from Pluk, the number of Patsaks traveling to this planet from Pluk, the number of Chatlanians traveling from this planet to Pluk, and the number of Patsaks traveling from this planet to Pluk. The total number of passengers does not exceed .
For each test, print the minimum number of times the tsak must be worn on the optimal route, followed by the order of visiting the planets separated by spaces. Planets listed in the input are numbered starting from one, and planet Pluk has number and always appears in the sequence twice — at the start and at the end. If there are several optimal routes, select the one where the planet with the smaller number is visited earlier.
For the full statement, see the original language version.
Example 1