NC53322. 管道监控
描述
某输气系统包含n个节点，编号分别为
，某些节点间有单向管道连接。1号节点是中央储气设施。
节点系统可用数列
来表示。对于
号节点会有一条通向i号节点的单向管道。已知中央储气设施可以将气体输送到系统中的所有节点。输气系统包含不同种类的管道，用英文小写字母a~z来表示。号节点通向i号节点的管道的类型为
。
有一种特殊的机器人被用来检查管道的质量。我们把「机器人从一个节点沿着一根管道前行到另一个节点，且机器人前进方向与气体方向一致」称作「一次移动」。
机器人会先被放在一个节点中，然后它会进行一次或多次移动，最后被人从输气系统中取出。这被称为「机器人进行了一次执勤」。
每次执勤时都需遵循m种「规格」中的其中一种，这些规格的编号分别为
。每种规格都用一个由英文小写字母组成的字符串
来表示。如果在一次执勤中机器人遵循了k号规范，则在这次执勤中，机器人移动的次数与)
相等，并且对于%5D%2C)
等于机器人第j次经过的管道的编号。
若某次执勤遵循了t号规格，则这次的花费为
。
请问，要想让所有的管道都至少被检查一次，至少需要花费多少钱，并给出执勤路线的方案。
节点系统可用数列
有一种特殊的机器人被用来检查管道的质量。我们把「机器人从一个节点沿着一根管道前行到另一个节点，且机器人前进方向与气体方向一致」称作「一次移动」。
机器人会先被放在一个节点中，然后它会进行一次或多次移动，最后被人从输气系统中取出。这被称为「机器人进行了一次执勤」。
每次执勤时都需遵循m种「规格」中的其中一种，这些规格的编号分别为
若某次执勤遵循了t号规格，则这次的花费为
请问，要想让所有的管道都至少被检查一次，至少需要花费多少钱，并给出执勤路线的方案。
输入描述
n,m,t（t的含义会在下面告诉你）
接下来n-1行：
接下来m行：
输出描述
第一行包含一个整数，表示最小花费。若无解请输出-1.
若t=0就不用管后续了，若t=1且有解则需输出方案。
输出方案时，在第一行输出最小花费之后，第二行应包含方案中路径的数量k，接下来k行，每行包括三个整数
示例1
输入:
3 3 0 1 a 2 b 3 a 4 b 2 a
输出:
6
示例2
输入:
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
说明:
