1753. Маршрут

Далеко не все в Тентуре имеют право носить малиновые штаны, и конечно, не все владеют пепелацем с гравицапой, поэтому для большинства жителей проблема перемещения между планетами была неразрешимой. Но с некоторых пор один предприимчивый чатланин с планеты Плюк вышел на рынок пассажирских перевозок, и за немного чатлов, готов перевозить желающих с планеты на планету. Рейс начинается с планеты Плюк, включает нескольких других планет, и завершается там же, на планете Плюк. Однако при подготовке рейса возникли неожиданные проблемы. Например, если чатланин с планеты Плюк хочет попасть на планету, которая является в рейсе предпоследней – ему невольно придётся посетить все планеты, которые находятся в рейсе между планетой Плюк и его точкой назначения. Очевидно, что часть планет в этом списке могут оказаться пацакскими. Но каждый чатланин обязан носить цак на пацакской планете и, наоборот, каждый пацак должен носить цак на чатланской планете. (Цак — колокольчик для носа, знак отличия для относительно низшей касты на данной планете). А процедура ношения цака унизительна во всех смыслах этого слова…

Поскольку данное бюро путешествий пока не имеет представительств на других планетах, перевозка осуществляется только с планеты Плюк на какую-либо другую, либо с другой планеты на Плюк. Задача планирования рейса упрощается – можно посещать планеты в произвольном порядке (но нельзя посещать одну и ту же планету дважды – в пути может закончиться луц). Необходимо вычислить такой порядок посещения планет, при котором надевать цак на промежуточных планетах придётся минимальное количество раз.

Первая строка входа содержит количество тестов. Первая строка каждого теста содержит число `N` (`N\ ≤\ 22`) – количество планет, обслуживаемых данным рейсом (не считая планеты Плюк). `N` следующих строк содержат информацию о планетах, в следующем виде: тип планеты (латинская заглавная буква С – чатланская, P – пацакская), количество чатлан, следующих до этой планету с Плюка, количество пацаков, следующих до этой планеты с Плюка, количество чатлан, с данной планеты на Плюк, количество пацаков, с данной планеты на Плюк. Всего пассажиров `≤\ 1000`.

Для каждого теста в выходной файл выводится, сколько раз придётся надевать цак при оптимальном маршруте, затем порядок посещения планет через пробел. Планеты, перечисленные во входном файле, нумеруются начиная с единицы, планета Плюк имеет номер ноль и всегда указывается в последовательности дважды – в начале и в конце последовательности. Если существуют несколько оптимальных маршрутов – выбирать тот, где планета с меньшим номером посещается раньше.

2
2
C 1 4 5 2
P 2 5 1 4
4
C 3 0 0 0
C 3 0 0 1
C 3 0 0 1
C 3 0 0 1

5 0 2 1 0
3 0 1 2 3 4 0

Комментарии к примеру: в первом рейсе возможны два варианта маршрута: 0 1 2 0 и 0 2 1 0. В первом варианте при посадке на чатланской планете 1 пятерым пацакам, которые следуют транзитом к своей планете 2, придётся надеть цак, а при следующей посадке на пацакской планете 2, пятерым чатланинам, которые сели на планете 1 и следуют до Плюка, также придётся надеть цак. Итого в первом варианте маршрута цак надевается 10 раз. В варианте 2 цак на промежуточных посадках надевается 4 и 1 раз соответственно, всего 5 раз. Второй вариант предпочтительнее.

Во втором рейсе все планеты чатланские, поэтому надевать цак придётся только пацакам. С Плюка пацаки не отправляются, но прибывают с трёх разных планет по одному. Первой посещается единственная планета, где пацак не заходит в пепелац, затем следуют три планеты с одинаковым набором пассажиров – на втором шаге из трёх оставшихся равноценных планет выбирается планета номер 2 как имеющая наименьший номер, затем 3 и оставшаяся 4. Пассажир с последней планеты не имеет промежуточных посадок, предпоследней совершает одну посадку и надевает цак 1 раз, и оставшийся пассажир надевает цак на двух промежуточных остановках, итого цак надевается 3 раза.