Courses

算法

线性枚举

Module: 线性枚举

Problem

5 /5

接触者追踪

Problem

农夫约翰继续照顾他的奶牛的健康，连续编号为 1…N。
最近，FD 对他们进行了检查，发现其中一些人生病了。使用来自谷仓的视频，FD 可以找出哪对奶牛相互作用传播了疾病。 FD 收集了一个列表，指示视频中奶牛对 (t,x,y) 发生交互的时间，这意味着在时间 t 奶牛 x 与奶牛 y 进行了交互。 FD 还知道以下内容：

最初只有一头牛被感染（零号患者）。
一旦奶牛被感染，她就会将感染传染给下一次 K 次互动（可能多次涉及同一伙伴）。传播K次后，她停止传播感染（意识到她正在感染，她开始彻底清洗她的蹄子）。
一旦她生病了，她就会一直生病。

不幸的是，PD 不知道他的 N 头牛中哪一头是“零号病人”，也不知道 K! 的值。帮助他根据他的数据缩小这些未知数的范围。答案保证存在。

输入
第一行输入包含 N (2≤N≤100) 和 T (1≤T≤250)。下一行包含一个长度为 N 的字符串，由 0 和 1 组成，描述了 N FD 奶牛的当前状态，0-健康，1-生病。以下T行中的每一行描述了FD交互列表中的一个条目，由三个数字t，x，y组成，其中t是交互时间的正整数（t≤250），x和y是不同的整数interval 1…N,, 表示在时间T有哪些奶牛进行了交互。在一个时间T不会发生超过一次的交互。
印记
打印包含三个整数 x、y、z 的一行，其中 x 是可能是“零号病人”的不同奶牛的数量y - 适合输入数据的 K 的最小可能值 z - 适合输入数据的 K 的最大可能值如果 K 没有上限，则打印“Infinity”；对于 z。请注意，K=0 是可能的。