AT_abc197_f.[ABC197F] Construct a Palindrome

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个包含 $N$ 个顶点和 $M$ 条边的连通无向图（不一定是简单图）。
第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$ ，并且上面写有一个字母 $C_i$ 。
你可以从顶点 $1$ 走到顶点 $N$ ，路径上可以多次经过同一条边或顶点。
请任选一条这样的路径，将经过的边上的字母按顺序排列，得到一个字符串。
请判断是否存在使得该字符串为回文串的路径。如果存在，求所有可能的回文串中最短的长度；如果不存在，输出 $-1$ 。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$A_3$ $B_3$ $C_3$
$\vdots$
$A_M$ $B_M$ $C_M$

输出格式

如果可以构造出回文串，输出所有可能回文串长度的最小值；否则输出 $-1$ 。

输入输出样例

输入#1

输出#1

输入#2
```
4 5
1 1 a
1 2 a
2 3 a
3 4 b
4 4 a
```
输出#2
```
5
```
输入#3
```
3 4
1 1 a
1 2 a
2 3 b
3 3 b
```
输出#3
```
-1
```

说明/提示

限制条件

$2 \leq N \leq 1000$
$1 \leq M \leq 1000$
$1 \leq A_i \leq N$
$1 \leq B_i \leq N$
$C_i$ 是小写英文字母
给定的图是连通的

样例解释 1

按边 $1, 2, 3, 1, 2, 4, 5, 6, 7, 8$ 的顺序经过，得到的字符串为 abcabbacba，这是一个回文串。无法构造更短的回文串，因此答案为 $10$ 。

样例解释 2

按边 $2, 3, 4, 5, 5$ 的顺序经过，可以得到字符串 aabaa，这是一个回文串。注意可以多次经过同一条边或顶点。

样例解释 3

无法构造出回文串。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页