Problem
Lão nông John tiếp tục chăm sóc sức khỏe cho đàn bò số liên tiếp 1…N.
Gần đây, FD đã kiểm tra tất cả và phát hiện ra rằng một số người trong số họ đang bị bệnh. Sử dụng video từ chuồng trại, FD có thể tìm ra cặp bò nào tương tác với nhau để lây lan dịch bệnh. FD đã thu thập danh sách cho biết thời điểm diễn ra tương tác của các cặp bò trong video (t,x,y), nghĩa là tại thời điểm t bò x tương tác với bò y. FD cũng biết những điều sau:
- Chính xác một con bò đã bị nhiễm bệnh ban đầu (bệnh nhân số 0).
- Sau khi một con bò bị nhiễm bệnh, nó sẽ truyền bệnh cho các tương tác K tiếp theo của mình (có thể liên quan đến cùng một đối tác nhiều lần). Sau K lần lây truyền, cô ấy ngừng lây nhiễm (khi nhận ra rằng mình đang lây nhiễm, cô ấy bắt đầu rửa sạch móng guốc của mình).
- Một khi cô ấy ốm, cô ấy sẽ ốm mãi.
Thật không may, PD không biết N con bò nào của anh ta là "Bệnh nhân số 0" và anh ta không biết giá trị của K!. Giúp anh ấy thu hẹp phạm vi của những ẩn số này dựa trên dữ liệu của anh ấy. Câu trả lời chắc chắn là có.
Đầu vào
Dòng đầu tiên chứa N (2≤N≤100) và T (1≤T≤250). Dòng tiếp theo chứa một chuỗi có độ dài N, gồm 0 và 1, mô tả trạng thái hiện tại của N con bò FD, 0 - khỏe mạnh, 1 - ốm yếu. Mỗi T dòng sau đây mô tả một mục từ danh sách các tương tác FD và bao gồm ba số t, x, y, trong đó t là thời gian tương tác nguyên dương (t≤250), x và y là các số nguyên khác nhau trong khoảng 1…N, cho biết những con bò nào đã tương tác vào thời điểm T. Không có nhiều hơn một lần tương tác xảy ra tại một thời điểm T.
Dấu ấn
In ra một dòng chứa ba số nguyên x, y, z, trong đó x là số con bò khác nhau có thể là "bệnh nhân số 0" y - giá trị nhỏ nhất có thể của K phù hợp với dữ liệu đầu vào z - giá trị lớn nhất có thể của K phù hợp với dữ liệu đầu vào Nếu không có giới hạn trên cho K, hãy in "Infinity"; cho z. Lưu ý rằng K=0 là có thể.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
4 3
1100
7 1 2
5 2 3
6 2 4
| 1 1 vô cực |