#P1194. [HNOI2006]潘多拉的盒子
[HNOI2006]潘多拉的盒子
[HNOI2006] 潘多拉的宝盒
题目描述


输入格式


输出格式
输出一行一个数,表示最长升级序列的长度。
样例 #1
样例输入 #1
4
1 1
0
0 0
2 1
0
1 1
0 0
3 1
0
1 1
2 2
0 0
4 1
0
1 1
2 2
3 3
0 0
样例输出 #1
3
样例 #2
样例输入 #2
3
1 1
0
0 0
3 1
0
0 1
2 0
1 2
9 1
0
0 1
2 3
4 5
6 7
8 0
1 2
3 4
5 6
7 8
样例输出 #2
3
提示

图片题面文字补充
一个咒语机是确定性二进制自动机,由编号 到 的元件组成,初始处于元件0,信号为空串。若当前信号为 、所在元件为 ,下一时刻可以选择追加0并移动到 ,或追加1并移动到 。有些元件是输出元件;信号到达输出元件时可以输出,得到一个咒语源。
若咒语机 能产生的每个咒语源也都能被咒语机 产生,则称 是 的升级,即语言包含关系。并未要求真包含:行为相同的两台机器可以互相升级。升级序列中的机器编号必须两两不同;求序列的最大长度。
输入第一行正整数 ,,表示机器数。随后按编号0到S-1描述每台机器:第一行两个正整数 ,;第二行给出m个输出元件编号(0到n-1)。再有n行,第i行(i从0起)为 ,均在0到n-1之间。输出最长升级序列长度。