秋祭 | 静岡高校工学部
秋祭 | 静岡高校工学部
卬高杯
T君はとある自動車販売店に勤めています。ある日こんなプログラム(TrumpScript)が送られてきました。
# Make TrumpScript great again!
wall = '\u9664\u8349' * 9
tremendous = '\u7dba\u9e97' * 9
# Print the Trump-ish pattern
tell wall + tremendous + wall
America is great.
そこでT君は
大変申し訳ございません。直ちに除草徹底いたします。
と返信しました。
「直ちに」徹底するため、T君は除草について調べてみました。するとこの世界の木は「複数の木がつながっている」ということがわかりました。そしてT君は「女装王」という一度に複数の繋がった木を除草できる最強の除草剤があることを知りました。例えば`A`と`B`の木がつながっていた時、`A`に除草剤を掛けるだけで二つの木を除草することができ、さらに`C`という木もつながっていれば`A`,`B`,`C`の3つの木を一度にまとめて除草できます。
T君は優秀な社員なので自店舗だけではなく同じ道の他店舗でも「環境整備活動」を行おうと考えています。具体的にはその店舗から`P \ [m]`ずつ離れた(合計で`1+2P \ [m]`の範囲)店舗の前の木を「環境整備」しようと考えています。
店舗は`N`店舗、木は`M`本あり、店舗、木の位置は道の一番左を`0 \ [m]`としてそれぞれ`B_i,T_j`(`1\leq i \leq N,1\leq j \leq M`)として与えられます。
また、事前の調査によって木`u_k`と木`v_k`(`1 \leq k \leq X`)が繋がっているということが分かっています。(木の連結関係は`X`個あります。)
T君は除草剤費を自腹で払うよう指導されているので、T君の自腹です。そのため、できるだけ使用する除草剤の量を少なくしたいです。
最小の除草剤購入数を求めてください。ただし、除草剤1つにつき1回の除草ができます。