HISTORY - History of Languages

Please click here to download a PDF version of the contest problems. The problem is problem H in the PDF. Remember that you must use stdin/stdout at SPOJ.


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.

For those of you who are unfamiliar with the concept of deterministic finite automata, you may use the following information:

A deterministic finite automata (DFA) is a 5-tuple, (S, Σ, T, s, A), consisting of:

  • a finite set of states (S)
  • a finite set called the alphabet (Σ)
  • a transition function (T : S × Σ→S)
  • a start state (s ∈ S)
  • a set of accept states (A ⊆ S)

Let M be a DFA such that M = (S, Σ, T, s, A), and X = x0x1 ... xn be a string over the alphabet Σ. M accepts the string X if a sequence of states, r0, r1 ... rn, exists in S with the following conditions:

  1. r0 = s
  2. ri + 1 = T(ri, xi), for i = 0 ... n - 1
  3. rn ∈ A.

- Wikipedia

Input

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, X0, X1 ... XT-1, (F ∈ {0, 1}, -1 ≤ Xi < N). If F = 1, then the state is an accepting state; also, if Xi = -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.

Output

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

Example

Input:
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

Output:
Case #1: No
Case #2: Yes

Added by:Fudan University Problem Setters
Date:2009-11-01
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 C99 GOSU NODEJS OBJC PERL6 VB.NET
Resource:ACM/ICPC Regional Contest, Hangzhou 2008

hide comments
2023-02-04 17:19:30 Simes
I've extracted the problem from the PDF. I hope that's ok? If there are any mistakes or discrepancies, assume the PDF is correct.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.