Газораспределительная система одного региона устроена следующим образом. Она
содержит n узлов, пронумерованных от 1 до n, некоторые узлы соединены односторонними
трубами. Узел с номером 1 соответствует центральному газохранилищу.
Система узлов описывается числами от p2, p3, …, pn. Для всех i от 2 до n узел с
номером pi соединен односторонней трубой с узлом i, газ по этой трубе передается от узла pi
к узлу i. Известно, что возможно доставить газ по трубам от центрального газохранилища до
любого узла системы (возможно, с использованием промежуточных узлов). В системе
используются трубы различных типов, тип трубы обозначается буквой английского алфавита
от «a» до «z». Труба, соединяющая узел pi с узлом i, имеет тип ci.
Для проверки качества труб используется специальный робот. Он помещается в
систему труб в одном из узлов и перемещается по трубам, каждый раз проверяя трубу, по
которой он перемещается. Робот может перемещаться по трубам только в том же
направлении, в котором по трубе передается газ. Совершив одно или несколько
перемещений по трубам между узлами, робот извлекается из системы труб.
Каждый запуск робота должен соответствовать одной из m заданных спецификаций,
пронумерованных от 1 до m. Спецификация с номером t представляет собой строку st,
состоящую из строчных букв английского алфавита. Запуск соответствует спецификации st,
если количество перемещений робота по трубам во время запуска совпадает с длиной st, и
для всех j от 1 до длины st на j-м шаге робот перемещается по трубе, тип которой совпадает с
st[j] —символом на позиции j в спецификации.
Если запуск робота соответствует спецификации с номером t, то стоимость этого
запуска составляет wt. Оператору системы необходимо проверить все трубы, для этого
можно запускать робот несколько раз. Каждый раз выбирается спецификация и маршрут
робота по трубам, соответствующие выбранной спецификации. Необходимо проверить все
трубы так, чтобы суммарная стоимость запусков робота для проверки качества труб была
минимальна. Одну и ту же трубу можно проверять несколько раз.
Требуется написать программу, которая по описанию системы труб и списку
спецификаций определяет минимальную суммарную стоимость запусков робота, в
результате которых все трубы будут проверены, а также список необходимых для этого
запусков (по требованию).
Формат входных данных
В первой строке входных данных находятся три целых числа n, m и t — количество
узлов системы труб, количество спецификаций запусков робота и параметр, указывающий,
требуется ли вывести список запусков робота или только их минимальную суммарную
стоимость (1 ≤ n ≤ 500, 1 ≤ m ≤ 105, t равно 0 или 1).
В последующих (n – 1) строках содержится информация о трубах, (i – 1)-я из этих
строк содержит разделенные пробелом значения pi и ci, где pi — целое число, задающее
номер узла, из которого ведет труба в i-й узел, а ci — строчная буква английского алфавита,
задающая тип этой трубы (1 ≤ pi ≤ i – 1).
В последующих m строках содержится информация о спецификациях, i-я из этих
строк содержит разделенные пробелом целое число wi — стоимость запуска робота в
соответствии с этой спецификацией, и состоящую из строчных букв английского алфавита
строку si — саму спецификацию (1 ≤ wi ≤ 10
9). Суммарная длина строк si не превышает 10
6.
Формат выходных данных
Первая строка выходных данных должна содержать одно число — минимальную
суммарную стоимость запусков робота, в результате которых все трубы будут проверены.
Если проверить все трубы невозможно, требуется вывести «–1».
Если t = 0, то больше ничего выводить не требуется.
Если t = 1 и проверить трубы возможно, то далее следует вывести список описаний
запусков робота. В этом случае вторая строка выходных данных должна содержать
число k — количество запусков робота, которое необходимо выполнить для проверки труб. В
следующих k строках необходимо вывести по три целых числа ai, bi и ci — номер узла, в
котором начинается запуск, номер узла, в котором заканчивается запуск, и номер
спецификации, которой соответствует запуск.
Если оптимальных способов проверки несколько, требуется вывести любой из них.
| Ввод |
Вывод |
|
3 3 0
1 a
2 b
3 a
4 b
2 a
|
6 |
|
7 3 1
1 a
2 a
3 b
3 b
1 b
6 b
3 aab
5 b
2 ab
|
15
4
1 4 1
2 5 3
1 6 2
6 7 2
|
Пояснение к примеру
Система труб, заданная во втором примере входных данных, и оптимальный способ
проверки всех труб для этого случая приведены на рисунке ниже.
Необходимо обратить внимание на следующие моменты:
- трубу можно проверять несколько раз, так в приведенном примере дважды
проверена труба из узла 2 в узел 3;
- одну и ту же спецификацию разрешается использовать несколько раз, в
приведенном примере вторая спецификация используется дважды, для
проверки труб из узла 1 в узел 6 и из узла 6 в узел 7;
- робот может перемещаться по трубам только в том же направлении, по
которому по трубе передается газ, спецификацию «ab» нельзя использовать
для проверки труб по маршруту 2→1→6, так как робот не может
переместиться из узла 2 в узел 1.