{"problem":{"name":"[USACO20OPEN] Cowntact Tracing B","description":{"content":"由于高传染性的牛传染病 COWVID-19 的爆发，Farmer John 非常担忧他的奶牛们（编号为 $1\\ldots N$）的健康。 最近，Farmer John 对他的所有奶牛进行了检测，发现有一部分奶牛对该疾病的检测结果呈阳性。利用牛棚内的视频监控，他得以查看最近的奶牛之间的互动行为，结果发现奶牛们互相打招呼时，她们会握蹄，不幸的是这是一种会将疾病从一头奶牛传播给另一头奶牛的行为。Far","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9954"},"statements":[{"statement_type":"Markdown","content":"由于高传染性的牛传染病 COWVID-19 的爆发，Farmer John 非常担忧他的奶牛们（编号为 $1\\ldots N$）的健康。\n\n最近，Farmer John 对他的所有奶牛进行了检测，发现有一部分奶牛对该疾病的检测结果呈阳性。利用牛棚内的视频监控，他得以查看最近的奶牛之间的互动行为，结果发现奶牛们互相打招呼时，她们会握蹄，不幸的是这是一种会将疾病从一头奶牛传播给另一头奶牛的行为。Farmer John 汇总了一个添加了时间戳的清单，每条数据的形式为 $(t,x,y)$，表示在时间 $t$，奶牛 $x$ 与奶牛 $y$ 握了蹄。Farmer John 同时还知道以下信息：\n\n（一）他的农场上恰有一头奶牛最初带有携带疾病（我们将这头奶牛称为“零号病人”）。\n\n（二）一旦一头奶牛被感染，她会在接下来的 $K$ 次握蹄中传染疾病（可能会与同一头奶牛握蹄多次）。握蹄 $K$ 次后，她不再在此后的握蹄中传染疾病（因为此时她意识到了她会传染疾病，于是会仔细地洗蹄）。\n\n（三）一旦一头奶牛被感染，她会持续处于被感染状态。\n\n不幸的是，Farmer John 不知道他的 $N$ 头奶牛中的哪一头是零号病人，也不知道 $K$ 的值！基于他的数据，请帮助他缩小这些未知量的范围。保证至少有一种可能的情况。 \n\n## Input\n\n输入的第一行包含 $N$（$2\\le N\\le 100$）和 $T$（$1\\le T\\le 250$）。下一行包含一个长为 $N$ 的字符串，每个字符均为 $0$ 或 $1$，表述目前 Farmer John 的 $N$ 头奶牛的状态——$0$ 表示一头健康的奶牛，$1$ 表示一头染病的奶牛。以下 $T$ 行每行包含 Farmer John 的互动清单中的一条记录，由三个整数 $t$、$x$ 和 $y$ 组成，其中 $t$ 为一次互动发生的正整数时间（$t\\le 250$），$x$ 和 $y$ 为范围 $1\\ldots N$ 内的不同整数，表示时间 $t$ 握蹄的两头奶牛。在每一时刻至多只有一次互动发生。 \n\n## Output\n\n输出一行，包含三个整数 $x$、$y$ 和 $z$，其中 $x$ 为可能为零号病人的奶牛数量，$y$ 为与数据一致的最小可能 $K$ 值，$z$ 为与数据一致的最大可能 $K$ 值（如果通过数据无法推断 $K$ 的上界，$z$ 输出 `Infinity`）。注意可能有 $K=0$。 \n\n[samples]\n\n## Note\n\n### 样例解释 1\n\n唯一可能是零号病人的是奶牛 $1$。对于所有的 $K>0$，奶牛 $1$ 在时刻 $7$ 感染奶牛 $2$，而奶牛 $3$ 和奶牛 $4$ 均不会被感染。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9954","tags":["模拟","2020","USACO","O2优化","枚举","排序"],"sample_group":[["4 3\n1100\n7 1 2\n5 2 3\n6 2 4","1 1 Infinity"]],"created_at":"2026-03-03 11:09:25"}}