Задача №113760. Мониторинг труб

Газораспределительная система одного региона устроена следующим образом. Она содержит n узлов, пронумерованных от 1 до n , некоторые узлы соединены односторонними трубами. Узел с номером 1 соответствует центральному газохранилищу. Система узлов описывается числами от p 2 , p 3 , ..., p n . Для всех i от 2 до n узел с номером p i соединен односторонней трубой с узлом i , газ по этой трубе передается от узла p i к узлу i . Известно, что возможно доставить газ по трубам от центрального газохранилища до любого узла системы (возможно, с использованием промежуточных узлов). В системе используются трубы различных типов, тип трубы обозначается буквой английского алфавита от «a» до «z». Труба, соединяющая узел p i с узлом i , имеет тип c i .

Для проверки качества труб используется специальный робот. Он помещается в систему труб в одном из узлов и перемещается по трубам, каждый раз проверяя трубу, по которой он перемещается. Робот может перемещаться по трубам только в том же направлении, в котором по трубе передается газ. Совершив одно или несколько перемещений по трубам между узлами, робот извлекается из системы труб.

Каждый запуск робота должен соответствовать одной из m заданных спецификаций , пронумерованных от 1 до m . Спецификация с номером t представляет собой строку s t , состоящую из строчных букв английского алфавита. Запуск соответствует спецификации s t , если количество перемещений робота по трубам во время запуска совпадает с длиной s t , и для всех j от 1 до длины s t на j -м шаге робот перемещается по трубе, тип которой совпадает с s t [ j ] —символом на позиции j в спецификации.

Если запуск робота соответствует спецификации с номером t , то стоимость этого запуска составляет w t . Оператору системы необходимо проверить все трубы, для этого можно запускать робот несколько раз. Каждый раз выбирается спецификация и маршрут робота по трубам, соответствующие выбранной спецификации. Необходимо проверить все трубы так, чтобы суммарная стоимость запусков робота для проверки качества труб была минимальна. Одну и ту же трубу можно проверять несколько раз.

Требуется написать программу, которая по описанию системы труб и списку спецификаций определяет минимальную суммарную стоимость запусков робота, в результате которых все трубы будут проверены, а также список необходимых для этого запусков (по требованию)

Входные данные

В первой строке входных данных находятся три целых числа n , m и t — количество узлов системы труб, количество спецификаций запусков робота и параметр, указывающий, требуется ли вывести список запусков робота или только их минимальную суммарную стоимость ( 1 ≤ n ≤ 500 , 0 ≤ m ≤ 10 5 , t равно 0 или 1 ).

В последующих ( n – 1 ) строках содержится информация о трубах, ( i – 1 )-я из этих строк содержит разделенные пробелом значения p i и c i , где p i — целое число, задающее номер узла, из которого ведет труба в i -й узел, а c i — строчная буква английского алфавита, задающая тип этой трубы ( 1 ≤ p i i – 1 ).

В последующих m строках содержится информация о спецификациях, i -я из этих строк содержит разделенные пробелом целое число w i — стоимость запуска робота в соответствии с этой спецификацией, и состоящую из строчных букв английского алфавита строку s i — саму спецификацию ( 1 ≤ w i ≤ 10 9 ). Суммарная длина строк s i не превышает 10 6 .

Выходные данные

Первая строка выходных данных должна содержать одно число — минимальную суммарную стоимость запусков робота, в результате которых все трубы будут проверены. Если проверить все трубы невозможно, требуется вывести « -1 ».

Если t = 0 , то больше ничего выводить не требуется.

Если t = 1 и проверить трубы возможно, то далее следует вывести список описаний запусков робота. В этом случае вторая строка выходных данных должна содержать число k — количество запусков робота, которое необходимо выполнить для проверки труб. В следующих k строках необходимо вывести по три целых числа a i , b i и c i — номер узла, в котором начинается запуск, номер узла, в котором заканчивается запуск, и номер спецификации, которой соответствует запуск.

Если оптимальных способов проверки несколько, требуется вывести любой из них.

Примечание

Система труб, заданная во втором примере входных данных, и оптимальный способ проверки всех труб для этого случая приведены на рисунке ниже.

  1. трубу можно проверять несколько раз, так в приведенном примере дважды проверена труба из узла 2 в узел 3 ;
  2. одну и ту же спецификацию разрешается использовать несколько раз, в приведенном примере вторая спецификация используется дважды, для проверки труб из узла 1 в узел 6 и из узла 6 в узел 7 ;
  3. робот может перемещаться по трубам только в том же направлении, по которому по трубе передается газ, спецификацию ab нельзя использовать для проверки труб по маршруту 2→1→6 , так как робот не может переместиться из узла 2 в узел 1 .

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры
Входные данные
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
1 6 2
6 7 2
2 5 3
Сдать: для сдачи задач необходимо войти в систему