Farmer John is worried for the health of his cows (conveniently numbered 1 \ldots N as always) after an outbreak of the highly contagious bovine disease COWVID-19.

Recently, Farmer John tested all of his cows and found some of them to be positive for the disease. Using video footage from inside his barn, he is able to review recent interactions between pairs of cows --- it turns out that when cows greet each-other, they shake hooves, a gesture that can unfortunately spread the infection from one cow to another. Farmer John assembles a time-stamped list of interacting pairs of cows, with entries of the form (t, x, y), meaning that at time t, cow x shook hooves with cow y. Farmer John also knows the following:

(i) Exactly one cow on his farm could have started out carrying the disease (we'll call this cow "patient zero").

(ii) Once a cow is infected, she passes the infection along with her next K hoof shakes (possibly including the same partner cow several times). After shaking hooves K times, she no longer passes the infection along with subsequent hoof shakes (since at this point she realizes she is spreading the infection and washes her hooves carefully).

(iii) Once a cow is infected, she stays infected.

Unfortunately, Farmer John doesn't know which of his N cows is patient zero, nor does he know the value of K! Please help him narrow down the possibilities for these unknowns based on his data. It is guaranteed that at least one possibility is valid.

#4176 upload 2 done 1 how_to_reg 1

Cowntact Tracing timer 1s memory 128MB

#4176

Cowntact Tracing 1s 128MB