行路难

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

度度熊非常仰慕诗仙太白。这一天,它决定追寻仙人的踪迹,找到沧海中仙山之所在。

沧海之中有很多个岛屿,由于这些岛屿都和诗仙有一种神奇而莫名的关系,当你在一个岛屿上默念一句诗时,就会传送到另一个岛屿上去。度度熊现在在岛屿A上,它希望通过默念一系列诗句,能够被传送到岛屿B上。

如果可以,它还希望这些诗句连起来,字典序可以最小。此言尤美,是邪?

Input

第一行一个整数T,表示T组数据。

每组数据的第一行包含四个整数$N (2 \leq N \leq 50), M (0 \leq M \leq 500)$,A,B。表示N个岛屿,和M个神奇的诗句传送方法,以及度度熊的起点和目的地$(0 \leq A, B < N, A \ne B)$。

然后的M行,每行两个数字$s, t (0 \leq s, t < N)$和一个字符串S(字符串只包含小写字母,$1 \leq S的长度 \leq 6$),表示默念S可以从s传送到t,注意s和t可以相同。并且可能有多种传送方法从一个岛屿到另一个岛屿,另外,如果在一个岛屿上默念一句诗可以传送到多个岛屿上,你可以随心,选择任意一个。

Output

对于每组测试数据输出两行:

第一行输出"Case #i:",其中 I 代表第 I 组测试数据。

然后输出可以完成传送的方法连接起来后字典序最小的传送诗句,如果不存在,无论是不存在字典序最小的,还是不存在这样的传送方法,都输出"Tough way!"(没有引号)。

Sample Input

3 2 2 0 1 0 0 b 0 1 a 2 2 0 1 0 0 a 0 1 b 4 4 0 1 0 3 hi 0 2 hey 3 1 rishi 2 1 jude

Sample Output

Case #1: a Case #2: Tough way! Case #3: heyjude
Hint
对于样例2,可以无限的利用a使字典序更小。

Hint

hujie

Source

2015年百度之星程序设计大赛 - 复赛

提交代码