Truy vết dịch bệnh

Có $N$ con bò, một số bị bệnh. Có $T$ lần bắt tay (thời điểm $t$, giữa bò $x$ và $y$). Đúng 1 bò là "bệnh nhân số 0". Bò bệnh lây cho bò khỏe khi bắt tay, nhưng chỉ lây trong $K$ lần bắt tay đầu tiên sau khi nhiễm bệnh. Tìm: số bò có thể là bệnh nhân 0, giá trị $K$ nhỏ nhất và lớn nhất phù hợp.

Dữ liệu vào

• Dòng đầu: $N$ và $T$.
• Dòng thứ hai: xâu $N$ ký tự 0/1 (trạng thái cuối).
• $T$ dòng tiếp: $t_i$, $x_i$, $y_i$.

Dữ liệu ra

Ba giá trị: số bệnh nhân 0 khả thi, $K$ min, $K$ max (hoặc Infinity).

Ràng buộc

• $2\le N\le 100$, $1\le T\le 250$

Ví dụ