F. Наибольшая общая строка двух графов
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
stdin
вывод
stdout

Вам заданы два ориентированных графа G1 и G2. Вершины обоих графов помечены символами латинского алфавита. Разные вершины могут иметь одинаковые пометки, каждая вершина помечена ровно одним символом.

Проходя по маршруту в таком графе, можно получить строку: каждый маршрут v1, v2, ..., vk в графе (где (vi, vi + 1) является дугой для каждого 1 ≤ i < k) генерирует строку "lv1lv2... lvk", где lv означает метку вершины v. Маршрут может проходить через одни и те же вершины и дуги по несколько раз или даже вырождаться в отдельную вершину.

Итак, можно получить одно множество строк, используя маршруты в графе G1, и второе множество строк, используя маршруты в графе G2. Какова длина наибольшей общей строки этих двух множеств? Напишите программу, которая находит наибольшую длину и соответствующие маршруты в обоих графах.

Входные данные

Входные данные состоят из нескольких тестовых наборов. Каждый тестовый набор состоит из описания G1 и описания G2. Описание каждого графа начинается со строки, содержащей два целых числа n и m (1 ≤ n ≤ 500,  0 ≤ m ≤ 4000), где n означает число вершин, а m — число дуг. Следующая строка содержит n строчных символов латинского алфавита, i-й из этих символов означает метку вершины с номером i. Следующие m строк описывают дуги, по одной в строке. Дуга задается парой целых чисел xj, yj (1 ≤ xj, yj ≤ n) — номерами начальной и конечной вершин дуги. В графе могут быть петли и кратные дуги.

Тестовые наборы разделяются пустой строкой.

Выходные данные

Для каждого тестового набора выведите его номер и длину наибольшей общей строки. Если искомая длина бесконечна, выведите в качестве длины число "-1". В случае, если длина конечна, выведите еще две строки. Эти строки должны содержать номера вершин в соответствующих маршрутах в G1 и G2. Если ответов несколько, выведите любой из них.

Примеры
Входные данные
6 5
abacab
1 2
2 3
3 4
4 5
5 6
5 5
aabac
1 2
2 3
3 4
4 5
5 1

1 1
a
1 1
2 2
aa
1 2
2 1
Выходные данные
Case 1: 5
1 2 3 4 5
2 3 4 5 1
Case 2: -1