测试数据来自 system/2903

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　犬界病毒的升级版 “LZH-3” 又在小H的狗场爆发，该病毒通过接触传染。经对狗场的n只狗检测。小H掌握了小狗们染病的确切情况。

　　为搞清楚病毒是怎么传染开来的，小H查看了狗场监控视频，发现一些狗在放风玩耍时，有相互舔对方嘴的可耻行为，更不幸的是这是一种病毒传播的行为。小H和他的助手们统计了一个清单，记录了这些相互舔嘴的信息，每条记录的形式为： t a b，表示在时间 t，小狗 a 与小狗 b 相互舔了嘴。同时，小H同时还得知以下三方面的信息：

　　1、狗场中恰有一只小狗是最初的感染者，即零号病狗。
　　2、一旦一只小狗感染病毒，它会在接下来的K次舔嘴中传染病毒，K以后面的舔嘴行为不再会传播病毒。
　　3、一旦一只小狗被感染，她会持续处于被感染状态。

　　遗憾的是，小H并不知道他的n只小狗中的哪一只才是零号病狗（即最先得病的狗），也不知道K的值范围！请帮助他推断这些未知量。保证至少有一种可能的情况。

【输入格式】

　　输入的第一行包含 n（2≤n≤100）和 m（1≤m≤250）。
　　第二行包含一个长为 n 的字符串，每个字符均为 0 或 1，表示当前n只小狗的状态：0 表示一只健康狗，1 表示一只病狗。
　　下面的m行每行包含一条记录：t a b，表示在时间t小狗a和小狗b发生了一次舔嘴行为。其中t是1..250内的整数，a和b是1..n内的不同整数。注意：在每一时刻至多只有一次舔嘴发生。

【输出格式】

　　输出一行，包含三个整数 s、mink 和 maxk，其中s表示可能是零号病狗的小狗数量，maxk为与数据一致的最小可能K值，maxk为与数据一致的最大可能K值，如果无法推断K的最大值，则输出INF。注意可能有K=0。

【输入输出样例1】

　Input

4 3
1110
5 1 2
6 1 3
7 1 4

　Output

2 1 2

【样例1解释】

　　零号病狗可能是小狗1或小狗2。
　　当K=1时，即小狗在第一次舔嘴的行为中具有传染性，此时有符合染病情况1110的方案：若零号病狗是小狗2，它第一次与小狗1舔嘴，病毒传染给小狗1，接着小狗1的第一次与小狗3舔嘴，所以它会把病毒传染给小狗3。小狗1第二次与小狗4舔嘴，这次不会传染病毒。
　　K=2时，即小狗在前两次舔嘴的行为中具有传染性，此时有符合染病情况1110的方案：若零号病狗是小狗 1 ，它第一次与小狗 2 舔嘴，病毒传染给小狗2，小狗1第二次与小狗 3舔嘴，所以它会把病毒传染给小狗3。小狗1第三次与小狗4舔嘴，这次不会传染病毒。此时符合染病情况：1110
　　可K=3时，此时没有符合染病情况1110的方案：若零号病狗是小狗 1 ，它的三次舔嘴都会传染病毒，即小狗2、小狗3、小狗4都会被传染。
　　所以 K 的最小值为1，最大值为2。

【输入输出样例2】

　Input

4 3
0110
4 2 3
1 3 4
3 3 1

　Output

1 1 INF

【样例2解释】

　　唯一可能是零号病狗的是小狗 2。对于所有的 K>0，小狗 2 在时刻 4 感染小狗 3，而小狗 4 和小狗 1 均不会被感染。

【数据限制】

　　对于 \(100\%\) 的数据，\(2≤n≤100\)，\(1≤m≤250\)。

【来源】

　　Mr.he