度度熊非常仰慕诗仙太白。这一天，它决定追寻仙人的踪迹，找到沧海中仙山之所在。
沧海之中有很多个岛屿，由于这些岛屿都和诗仙有一种神奇而莫名的关系，当你在一个岛屿上默念一句诗时，就会传送到另一个岛屿上去。度度熊现在在岛屿A上，它希望通过默念一系列诗句，能够被传送到岛屿B上。
如果可以，它还希望这些诗句连起来，字典序可以最小。此言尤美，是邪？
第一行一个整数 T，表示 T 组数据。
每组数据的第一行包含四个整数 N（2 \le N \le 50），M（0 \le M \le 500），A，B。表示 N 个岛屿，和 M 个神奇的诗句传送方法，以及度度熊的起点和目的地（0 \le A,B < N，A \neq B）。
然后的 M 行，每行两个数字 s,t（0 \le s,t < N）和一个字符串 S（字符串只包含小写字母，1 \le |S| \le 6），表示默念 S 可以从 s 传送到 t，注意 s 和 t 可以相同。并且可能有多种传送方法从一个岛屿到另一个岛屿，另外，如果在一个岛屿上默念一句诗可以传送到多个岛屿上，你可以随心，选择任意一个。
对第i组数据，输出
Case \ i:
然后输出两座山峰的ID (从1开始)，如果有多组答案，输出字典序最小的一对。