COWVID-19 Transmission Analysis

Farmer John is worried about the outbreak of the highly contagious cow disease \(COWVID\text{-}19\) among his \(N\) cows (numbered \(1\ldots N\)). After testing, some cows have returned positive results. Using video surveillance from his barn, Farmer John obtained a list of handshake interactions among the cows. In each interaction, two cows shake hooves, which may transmit the disease.

The following facts are known:

• Exactly one cow was initially infected; this cow is referred to as the patient zero.
• Once a cow is infected, it will transmit the disease in its next \(K\) handshakes (even if it shakes the same cow more than once). After \(K\) handshakes, the cow stops transmitting (as it starts to take precautions).
• Once infected, a cow remains infected permanently.

Given the final infection status of all cows and a list of \(T\) interactions in the form \( (t,x,y) \) (indicating that at time \(t\), cow \(x\) shook hooves with cow \(y\)), determine:

- The total number of possible patient zero candidates,
- The smallest possible value of \(K\), and
- The largest possible value of \(K\) (or output "Infinity" if \(K\) can be arbitrarily large).

The input starts with two integers \(N\) and \(T\). The next line is a binary string of length \(N\) representing the final infection statuses (with '1' indicating infected and '0' indicating uninfected). This is followed by \(T\) lines each containing three integers \(t\), \(x\), and \(y\) describing an interaction.

inputFormat

The first line contains two space-separated integers \(N\) and \(T\): the number of cows and the number of interactions.

The second line contains a binary string of length \(N\) representing the final infection status of each cow (1 for infected, 0 for not infected).

Each of the following \(T\) lines contains three space-separated integers \(t\), \(x\), and \(y\), meaning that at time \(t\), cow \(x\) shook hooves with cow \(y\).

outputFormat

Output a single line with three space-separated values: the number of possible patient zero candidates, the smallest possible value of \(K\), and the largest possible value of \(K\) (or "Infinity" if there is no upper bound).

sample

3 2
110
1 1 2
2 2 3

1 1 1