主君もまた、これらすべての事柄において、忠実な封臣に対して同じ義務を果たさなければならない。
- シャルトルのフルベール、アキテーヌ公ギヨームへの書簡（1020年）
あなたは王国の道路を担当する役人ですが、最近、街道に強盗が出没するようになり、頭を悩ませています。この状況を解決するため、国王は配下の領主たちに騎士を出して警備隊を編成し、道路の治安と安全を守るよう命じようとしています。しかし、領主ごとに出せる騎士の人数が異なるため、すべての道路に騎士を配置できるとは限りません。
王国には国王を含めて から までの番号が付いた 人の領主がいます。 番の領主が国王です。国王以外の各領主はちょうど一人の主君に仕え、その主君の封臣です。どの領主からでも主君を順にたどると国王に到達します。
各領主は、領地と呼ばれる自分の土地を一つずつ治めています。 番の領主の主君は 番の領主で、国王以外の各領主の領地は、その主君の領地と一本の道路で結ばれています。
王国には、主君と封臣の関係にない領主同士の領地を結ぶ道路もあるかもしれません。しかし、国王は主君と封臣の間の往来を優先して守ろうとしています。そのため、警備隊を配置する対象は、各領主の領地とその主君の領地を結ぶ道路に限ります。ほかの道路はこの問題では考慮しません。
道路に配置する警備隊は、その両端の領主が騎士を一人ずつ出して編成します。 番の領主は治安維持に参加する騎士を 人出せます。各騎士は一つの警備隊にしか参加できず、各道路には警備隊を一つまで配置できます。すべての騎士を配置する必要はありません。
警備隊が配置された道路は安全な道路になります。対象となる道路のうち、安全な道路の本数の最大値を求めてください。
入力の一行目に領主の人数 が与えられます。
二行目に が空白区切りで与えられます。
安全な道路の本数の最大値を出力してください。
一つ目の例では、 番と 番の領地を結ぶ道路、 番と 番の領地を結ぶ道路、 番と 番の領地を結ぶ道路に警備隊を配置できます。対象となるすべての道路は 番または 番の領地につながっています。この二人の領主が出せる騎士は合計 人なので、 本以上の道路に警備隊を配置することはできません。
三行目に が空白区切りで与えられます。
二つ目の例では、対象となるすべての道路が国王の領地につながっています。国王が出せる騎士がいないため、警備隊を配置できません。
