Nông dân John lo lắng cho sức khỏe của những con bò (như mọi khi, chúng được đánh số thuận tiện từ \(1 \ldots N\)) sau khi căn bệnh truyền nhiễm rất mạnh ở bò COWVID-19 bùng phát.

Gần đây, Nông dân John xét nghiệm tất cả những con bò và phát hiện một số con dương tính với căn bệnh. Nhờ các đoạn phim ghi lại bên trong chuồng, ông có thể xem lại những lần tương tác gần đây giữa các cặp bò — hóa ra khi chào hỏi nhau, những con bò bắt tay bằng móng, một cử chỉ đáng tiếc là có thể truyền bệnh từ con bò này sang con bò khác. Nông dân John lập một danh sách các cặp bò tương tác có gắn mốc thời gian, với mỗi mục có dạng \((t, x, y)\), nghĩa là tại thời điểm \(t\), bò \(x\) đã bắt tay bằng móng với bò \(y\). Nông dân John còn biết những điều sau:

1. Chính xác một con bò trong trang trại có thể đã mang bệnh từ ban đầu (ta gọi con bò này là "bệnh nhân số 0").

2. Sau khi một con bò bị nhiễm bệnh, nó sẽ truyền bệnh qua \(K\) lần bắt tay bằng móng tiếp theo (có thể gồm nhiều lần với cùng một con bò). Sau khi bắt tay bằng móng \(K\) lần, nó không còn truyền bệnh qua những lần bắt tay bằng móng sau đó nữa (vì lúc này nó nhận ra mình đang làm lây bệnh và rửa móng thật kỹ).

3. Một khi đã bị nhiễm bệnh, con bò sẽ luôn bị nhiễm bệnh.

Đáng tiếc là Nông dân John không biết con nào trong số \(N\) con bò là bệnh nhân số 0, cũng không biết giá trị của \(K\)! Hãy giúp ông thu hẹp các khả năng của những đại lượng chưa biết này dựa trên dữ liệu đã có. Đề bài đảm bảo tồn tại ít nhất một khả năng hợp lệ.

Dữ liệu vào

Tệp tracing.in:

Dòng đầu tiên chứa \(N\) (\(2 \leq N \leq 100\)) và \(T\) (\(1 \leq T \leq 250\)). Dòng tiếp theo chứa một xâu độ dài \(N\) gồm các ký tự 0 và 1, mô tả trạng thái hiện tại của \(N\) con bò của Nông dân John — 0 biểu thị một con bò khỏe mạnh và 1 biểu thị một con bò hiện đang mắc bệnh. Mỗi dòng trong \(T\) dòng tiếp theo mô tả một bản ghi trong danh sách tương tác của Nông dân John và gồm ba số nguyên \(t\), \(x\), \(y\), trong đó \(t\) là thời điểm nguyên dương của lần tương tác (\(t \leq 250\)), còn \(x\) và \(y\) là hai số nguyên phân biệt trong phạm vi \(1 \ldots N\), chỉ ra những con bò đã bắt tay tại thời điểm \(t\). Tại mỗi thời điểm có nhiều nhất một lần tương tác.

Dữ liệu ra

Tệp tracing.out:

In một dòng gồm ba giá trị \(x\), \(y\) và \(z\), trong đó \(x\) là số con bò có thể là bệnh nhân số 0, \(y\) là giá trị nhỏ nhất có thể của \(K\) phù hợp với dữ liệu, và \(z\) là giá trị lớn nhất có thể của \(K\) phù hợp với dữ liệu (nếu không thể suy ra cận trên của \(K\) từ dữ liệu, in Infinity cho \(z\)). Lưu ý rằng \(K=0\) cũng có thể xảy ra.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Ví dụ

4 3
1100
7 1 2
5 2 3
6 2 4

1 1 Infinity

Nguồn

USACO 2020 US Open Contest, Bronze — Cowntact Tracing

Tác giả bài: Brian Dean.