题目描述

在数字系统的诸多领域(如工业系统离散事件控制、数字电路、程序的

语法分析等实际应用)中，有限自动机是用来抽象地表示系统行为的一种工

具。实际上，有限自动机是把系统表示成若干种可能的状态。在一定的外

部条件(称作输入)下，系统的状态会发生变化，同时系统也有相应的输出。

为了直观地表示，可以把这些状态画成小圆圈，同时每个状态都有一个不含空白字符的

字符串名字。状态间的变化可以画成弧，同时把状态发生变化的条件和发生变化时的输出在

弧上标出(如下图所示)。

有限自动机在每个状态下的输入、输出都是一个固定长度的二进制数串。但是在弧上标出的输入条件除了 0 和 1之外还有一个符号 X 。符号 X 表明该位既可以是 0 也可以是 1。当外部输入满足弧上所标的输入条件，有限自动机就会从当前状态转变到该弧所指向的那个状态。例如当前状态是 S1，输入是“01”(或“11”)，这时有限自动机就会转变成状态 S2，同时输出“10” 。在一个输入序列的作用下，有限自动机就会从一个状态转移到另一个

状态，不断地变化所处的状态，与此同时会产生一个输出序列。对有限自动机进行测试就是要找出一种叫做UIO 的输入序列。状态 s 的UIO 序列可以使状态 s 在该输入序列作用下的输出序列不同于任何其他状态在该序列作用下的输出序列。作为黑箱测试(不涉及内部结构，即看不见内部结构)的一种方法，UIO 序列只考察输出序列，而不考虑其他因素。

例如，序列长度为 1 的输入序列“01”就同时是状态 S1、 S2和 S3的UIO 序列。因为状态 S1在输入“01”作用下的输出是“10” ， 状态 S2在输入“01”作用下的输出是“01”, 状态 S3在输入“01”作用下的输出是“00” 。一般而言，同一个有限自动机不同状态的UIO 序列可以各不相同。实践表明，并不是所有有限自动机的任何一个状态都存在着UIO 序列。同时任何一个状态的UIO 序列经过任意拓展(即延长序列长度)仍然是该状态

的UIO 序列。通常我们特指某状态的最短UIO 序列为该状态的UIO 序列。现在请你编写程序确定有限自动机中存在着UIO 序列的状态数，同时求出这些存在着UIO 序列的那些状态的最短UIO 序列的序列长度最大值。

输入格式

输出格式

输出两个数据，中间用空白字符隔开。第一个数据表示该有限自动机中存在UIO 序列的状态数；第二个数据表示存在着UIO 序列的那些状态的最短UIO 序列的序列长度最大值。

X1 s1 s2 10
X0 s1 s3 11
01 s2 s1 01
1X s2 s3 00
X0 s2 s3 00
1X s3 s1 11
0X s3 s2 00

3 1