400399: GYM100162 F Longest Two Graphs Common String

You are given two directed graphs G₁ and G₂. The vertices of both graphs are labeled with lowercase English letters. Different vertices can have the same labels, each vertex is labeled with exactly one letter.

Moving along a path in a graph one may pronounce a string. So each path v₁, v₂, ..., v_k in a graph (where (v_i, v_i + 1) is an arc for each 1 ≤ i < k) generates a string "l_v1l_v2... l_vk", where l_v is the label of the vertex v. A path may contain cycles, it can degenerate to a single vertex.

One may pronounce set of strings using G₁ and set of strings using G₂. What is the length of the longest common string in two sets? Write a program which will find the required length and the corresponding paths in both graphs.

The input contains several test cases. Each test case consists of description of G₁ and description of G₂. Each description starts with the line containing integers n and m (1 ≤ n ≤ 500,  0 ≤ m ≤ 4000), where n is the number of vertices and m is the number of arcs. The next line contains a string of exactly n lowercase English letters, the i-th letter in the string stands for the label of the i-th vertex. The following m lines contain arcs, one arc description per line. Each description is a pair of integers x_j, y_j (1 ≤ x_j, y_j ≤ n) — the starting and finishing endpoints of the j-th arc. Graphs can contain loops and multiple arcs.

The test cases are separated with a blank line.

For each test case display the case number and the length of the longest common string. If the longest common string is infinite, display "-1" as the length. In the case of finite longest common string, display two additional lines. Lines should contain vertex indices along the corresponding path in G₁ and G₂. If there are multiple answers, display any of them.

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