#P12179. [2024年联测]士兵

[2024年联测]士兵

士兵(solider)

题目背景

我一定要去寻找。

就算无尽的星辰令我的探寻希望渺茫。

就算我必须单枪匹马。

题目描述

xie_lzh 给了你一张 nn 个点 mm 条边的有向图,每条边上有一个小写英文字母。

称一条路径为回文路径,当且仅当这条路径上的字母连起来之后是回文串。

xie_lzh 现在对你进行 qq 次询问,第 ii 次询问从 sis_i 到 tit_i 的所有路径中,最短的回文路径的长度是多少。

定义一条回文路径的长度为它经过的边的个数(即它的回文串的长度)。

输入格式

第一行3个整数 n,mn,m 和 tptp,其中 tptp 的含义见输出格式。

接下来 mm 行,每行两个整数 ui,viu_i,v_i 与一个字母 cic_i,表示有一条从 uiu_i 到 viv_i 的边,这条边上的字母是 cic_i。

第 m+1m+1 行一个整数 qq。

接下来 qq 行每行两个整数 sis_i 和 tit_i,表示一组询问。

输出格式

输出 qq 行,第 ii 行表示第 ii 次询问的答案。

如果这次无解,则输出 -1。

否则输出一个整数表示路径的长度,若 tp=1tp=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≤n≤1031\le n\le10^3,1≤m,q≤1051\le m,q\le10^5。

测试点 nn mm qq tptp 子任务依赖 分值
1 ≤5\le5 ≤10\le10 =1=1 0 10
2 ≤102\le10^2 ≤103\le10^3 ≤102\le10^2 1 15
3 ≤400\le400 ≤6×104\le6\times10^4 2 25
4 ≤103\le10^3 ≤105\le10^5 =0=0 0 10
5
6 3,4,5 30

对于子任务 4,满足 ci=ac_i=a。

对于子任务 5,满足 ci∈{a,b}c_i\in\{a,b\}。