问题 23769 --QiQi and Walk

23769: QiQi and Walk

时间限制: 3 Sec  内存限制: 128 MB
提交: 6  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

给一个有向图,无重边自环。每条边都有一个字母,现在给你一个查询数组Q,问你Q[i]到Q[i+1]的最短回文路径,并输出任意路径,如果不存在,输出-1。

输入

输入n和m表示图的点的个数和有向边的个数。接下来m行每行输入u,v,ch,表示存在一条u到v的有向边,边的字符是ch。然后输出一个q表示查询数组的长度是q,然后输入q个数,表示查询数组。2 <= n <= 400,1 <= m <= 60000,1 <= q <= 100。

输出

输出q-1行,第i行表示Q[i-1]到Q[i]的查询的查询。对于每个查询,如果存在路径,先输出路径的长度,然后输出路径字符串,不存在输出-1。

样例输入

6 7
1 2 a
1 3 x
1 4 b
2 6 l
3 5 y
4 5 z
6 5 a
3
1 5 3

样例输出

3 ala
-1

来源

 

[提交][状态]