#P12179. [2024年联测]士兵
[2024年联测]士兵
士兵(solider)
题目背景
我一定要去寻找。
就算无尽的星辰令我的探寻希望渺茫。
就算我必须单枪匹马。
题目描述
xie_lzh 给了你一张 个点 条边的有向图,每条边上有一个小写英文字母。
称一条路径为回文路径,当且仅当这条路径上的字母连起来之后是回文串。
xie_lzh 现在对你进行 次询问,第 次询问从 到 的所有路径中,最短的回文路径的长度是多少。
定义一条回文路径的长度为它经过的边的个数(即它的回文串的长度)。
输入格式
第一行3个整数 和 ,其中 的含义见输出格式。
接下来 行,每行两个整数 与一个字母 ,表示有一条从 到 的边,这条边上的字母是 。
第 行一个整数 。
接下来 行每行两个整数 和 ,表示一组询问。
输出格式
输出 行,第 行表示第 次询问的答案。
如果这次无解,则输出 -1。
否则输出一个整数表示路径的长度,若 ,则输出这条路径上的所有字母。
如果有多条满足条件的路径,任意输出一条即可。
样例 1
输入
5 10 1
2 4 m
4 3 u
2 3 a
5 3 o
3 5 m
2 3 r
3 5 j
1 3 j
3 2 o
3 1 r
3
1 2
3 1
2 5
输出
-1
1 r
3 mum
子任务
对于所有的数据,保证 ,。
| 测试点 | 子任务依赖 | 分值 | ||||
|---|---|---|---|---|---|---|
| 1 | 0 | 10 | ||||
| 2 | 1 | 15 | ||||
| 3 | 2 | 25 | ||||
| 4 | 0 | 10 | ||||
| 5 | ||||||
| 6 | 3,4,5 | 30 | ||||
对于子任务 4,满足 。
对于子任务 5,满足 。