ニナの啓発

ニナの啓発

問題文

林くんはプロの啓発者であり、人から人へと噂を伝えることで、陰謀論を広める活動をしています。

林くんは、陰謀論を広まる強さ$S$で吹き込むことが出来ます。

林くんが啓発対象としているグループには$N$人がいます。 このグループでは、一部の人同士が「直接の知り合い関係」にあります。

その関係は、$N-1$個の組($u_i$, $v_i$)として与えられます。

ある人物に陰謀論を伝えると、その人物は自分の知り合いに対して、同じ陰謀論を伝えてしまいます。 ただし、その際に広まる強さは1減衰します。

強さが0になった時点で、その陰謀論はそれ以上広がりません。

林くんは、何人か吹き込み対象を選ぶことで、グループ内の全員に陰謀論を行き渡らせたいです。

ただし、プロとして、混乱による騒ぎを防ぐため、「同一人物が二人以上から吹き込まれる」事態を防ぐよう、細心の注意を払います。

このとき、全員に陰謀論を行き渡らせるために、必要な吹聴数の最小値を求めてください。

不可能な場合は、$-1$を出力してください。

制約

• $0 \leq S \leq 10^5$
• $2 \leq N \leq 10^5$
• $1 \leq u_i, v_i \leq N$
• グラフは木である

入力例1

0 4
1 2
2 3
3 4

出力例1

4

入力例2

1 4
1 2
2 3
3 4

出力例2

2