P9954 [USACO20OPEN] Cowntact Tracing B

Due to the outbreak of the highly contagious cow disease COWVID-19, Farmer John is very worried about the health of his cows (numbered $1\ldots N$). Recently, Farmer John tested all of his cows and found that some of them tested positive for the disease. Using the barn’s surveillance videos, he was able to review recent interactions between cows. He found that when cows greet each other, they shake hooves; unfortunately, this is an action that can spread the disease from one cow to another. Farmer John compiled a timestamped list, where each record has the form $(t,x,y)$, meaning that at time $t$, cow $x$ shook hooves with cow $y$. Farmer John also knows the following information: (1) There is exactly one cow on his farm that initially carried the disease (we call this cow “patient zero”). (2) Once a cow becomes infected, she will spread the disease during her next $K$ hoofshakes (she may shake hooves with the same cow multiple times). After $K$ hoofshakes, she will no longer spread the disease in any future hoofshakes (because she then realizes she can spread the disease, so she will carefully wash her hooves). (3) Once a cow becomes infected, she will remain infected. Unfortunately, Farmer John does not know which of his $N$ cows is patient zero, nor does he know the value of $K$! Based on his data, please help him narrow down the possible values of these unknowns. It is guaranteed that at least one scenario is possible.

The first line of input contains $N$ ($2\le N\le 100$) and $T$ ($1\le T\le 250$). The next line contains a string of length $N$, where each character is $0$ or $1$, describing the current status of Farmer John’s $N$ cows: $0$ means a healthy cow, and $1$ means an infected cow. The next $T$ lines each contain one record from Farmer John’s interaction list, consisting of three integers $t$, $x$, and $y$, where $t$ is the positive integer time when an interaction occurred ($t\le 250$), and $x$ and $y$ are distinct integers in the range $1\ldots N$, indicating the two cows that shook hooves at time $t$. At most one interaction occurs at any given time.

Output one line containing three values $x$, $y$, and $z$, where $x$ is the number of cows that could be patient zero, $y$ is the minimum possible value of $K$ consistent with the data, and $z$ is the maximum possible value of $K$ consistent with the data (if the data cannot determine an upper bound for $K$, output `Infinity` for $z$). Note that $K$ may be $0$.

### Sample Explanation 1 The only possible patient zero is cow $1$. For all $K>0$, cow $1$ infects cow $2$ at time $7$, and cows $3$ and $4$ will not be infected. Translated by ChatGPT 5