Directions
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 affordable travel between planets for a few chatls. The journey begins and ends on the planet Pluk, with several stops on other planets in between.
During the planning of these journeys, some unexpected issues have arisen. For instance, if a Chatlanian from Pluk wants to reach a planet that is the second-to-last stop, they must visit all the planets between Pluk and their destination. Some of these planets might be Patsak planets. On a Patsak planet, every Chatlanian must wear a tsak, and on a Chatlanian planet, every Patsak must do the same. A tsak is a nose bell, a symbol of lower caste status on a given planet, and wearing it is considered humiliating.
Since the travel bureau currently operates only from Pluk to another planet or vice versa, the journey planning is simplified. Planets can be visited in any order, but no planet can be visited twice to avoid running out of luc. The goal is to determine the order of visiting planets that minimizes the number of times a tsak must be worn on intermediate planets.
Input
The first line of input specifies the number of tests. For each test, the first line contains the number N ≤ 22, representing the number of planets serviced by this journey (excluding Pluk). The next N lines provide information about each planet in the following format: the type of planet (Latin capital letter C for Chatlanian, P 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 is ≤ 1000.
Output
For each test, the output should display 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 are numbered starting from one, with planet Pluk being number zero, and it appears twice in the sequence—at the start and end. If multiple optimal routes exist, choose the one where the planet with the smaller number is visited first.
Comments on the example: In the first journey, there are two possible routes: 0 1 2 0, and 0 2 1 0. In the first option, upon landing on the Chatlanian planet 1, five Patsaks transiting to their planet 2 must wear a tsak. On the next landing on the Patsak planet 2, five Chatlanians who boarded on planet 1 and are heading to Pluk must also wear a tsak. Thus, in the first route, the tsak is worn 10 times. In the second option, the tsak is worn 4 and 1 times respectively on intermediate stops, totaling 5 times. The second option is better.
In the second journey, all planets are Chatlanian, so only Patsaks must wear a tsak. Patsaks do not depart from Pluk but arrive from three different planets, one each. The first visited planet is the only one where a Patsak does not board the pepelats. Then, there are three planets with the same passenger set. On the second step, from the three equivalent remaining planets, planet number 2 is chosen as it has the smallest number, followed by 3, and finally 4. The passenger from the last planet has no intermediate stops, the penultimate one makes one stop and wears a tsak 1 time, and the remaining passenger wears a tsak on two intermediate stops, totaling 3 times.