Courses

アルゴリズム

線形列挙

Module: 線形列挙

Problem

5 /5

連絡先の追跡

Problem

農夫のジョンは、連続番号 1…N の牛たちの健康に気を配り続けています。
最近、FD が全員をチェックしたところ、一部が病気であることがわかりました。納屋からのビデオを使用して、FD はどのペアの牛が相互作用して病気を広めたかを突き止めることができます。 FD は、ビデオ (t,x,y) 内の牛のペアの相互作用が発生した時刻を示すリストを収集しました。これは、時刻 t に牛 x が牛 y と相互作用したことを意味します。 FD は次のことも認識しています。 <オール>

正確に 1 頭の牛が最初に感染しました (患者ゼロ)。

牛が感染すると、次の K 回の接触 (同じパートナーが複数回関与する可能性があります) に感染が移ります。 K 回の伝染の後、彼女は感染の伝染を停止します (感染していることに気づき、ひづめを徹底的に洗い始めます)。

一度病気になると、ずっと病気のままです。

残念ながら、PD は自分の N 頭の牛のうちどれが「患者ゼロ」であるかを知りません。また、K! の値も知りません。彼のデータに基づいて、これらの未知数の範囲を絞り込むのを手伝ってください。答えは必ず存在します。

入力
最初の入力行には、N (2≤N≤100) と T (1≤T≤250) が含まれます。次の行には、0 と 1 で構成される長さ N の文字列が含まれており、N 頭の FD 牛の現在の状態 (0 - 健康、1 - 病気) を記述しています。次の各 T 行は、FD インタラクションのリストからのエントリを記述し、t、x、y の 3 つの数値で構成されます。ここで、t は正の整数のインタラクション時間 (t<250) であり、x と y は、間隔 1…N, は、時間 T にどの乳牛が相互作用したかを示します。一度の時間 T で複数の相互作用が発生することはありません。
インプリント
x、y、z の 3 つの整数を含む 1 行を出力します。ここで、x は「患者ゼロ」になる可能性のある異なる牛の数です。 y - 入力データに適合する K の可能な最小値 z - 入力データに適合する K の可能な最大値 K の上限がない場合は、"Infinity" を出力します。 z の場合。 K=0 の可能性があることに注意してください。