History of Languages

We are examining two specific classes of languages (a possibly infinite set of
strings) in this problem. Fortunately (or maybe unfortunately), we are not given the strings contained in each language directly, rather we are given two deterministic finite automatons that describe such languages.

Your task here is simple: to determine if the languages described by the two automatons are the same.

There are multiple test cases in the input file.
The first line of each test case is one integer, T ( 2 ÷ T ÷ 26), the size of the alphabet. In each test case, the description of automaton A comes before that of automaton B. The description of each automaton starts with one line containing N (1 ÷ N ÷ 2000 ), the number of states in the automaton, followed by N lines, each line of the format: F, X₀, X₁, ˇ, X_T-1, ,-1 ÷ X_i < N). If F = 1, then the state is an accepting state; also, if X_i = -1, it means that the state has no corresponding transition available for character i. The start state of both finite automatons will always be state 0.

Two successive test cases are separated by a blank line. A case with a single 0 indicates the end of the input file, and should not be processed by your program.

For each test case, please print “Yes” if the two languages described by the
automatons are equivalent; output “No” otherwise.

2
3
1 -1 1
0 -1 2
0 -1 0
2
1 -1 1
0 -1 0
3
4
1 -1 -1 1
1 -1 -1 2
1 -1 -1 3
1 -1 -1 1
2
1 -1 -1 1
1 -1 -1 0
0

Case #1: No
Case #2: Yes

2008 Asia Regional Hangzhou