题目描述

给定两个确定性有限状态自动机（DFA）$A,B$，判断 $A$ 和 $B$ 是否等价（即对于任意输入串，输出都一致）。

输入格式

输入有若干组数据，对于每一组输入数据：

第一行一个正整数 $m$ 表示字符集大小。

接下来描述 $A$ 和 $B$，对于每一个 DFA：

第一行一个整数 $n$ 表示状态数。

接下来 $n$ 行，第 $i+1$ 行有 $m+1$ 个数 $F_i,x_{i0},x_{i1},\cdots,x_{im-1}$，$F_i$ 表示状态 $i$ 是否为终态，若 $F_i=1$ 表示状态 $i$ 是终态，否则不是；$x_{ic}$ 表示状态 $i$ 通过字符 $c$ 转移到状态 $x_{ic}$，若 $x_{ic}=-1$ 则表示无此转移边。

输出格式

对第 $i$ 组数据，输出单独一行 Case #i: Yes 或者 Case #i: No 表示第 $i$ 组数据中两个 DFA 是否等价。

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

数据规模与约定

$1\le n \le 2000$，$2\le m\le 26$。