Delete and Delete

配点： 点

頂点からなり、頂点 を根とする根付き木があります。頂点 の親は頂点 です。 これからあなたは以下の操作を繰り返します。

• 根以外の頂点が存在するなら、それらのうち一つを選び削除する。その後、葉となっている根以外の頂点を全て削除する。
  • ここで頂点 が削除された場合、頂点 の子である頂点の新しい親は頂点 となる。

根以外の頂点を全て削除するまでに行う操作の回数の最小値を求めてください。

• 入力はすべて整数

答えを出力し、最後に改行してください。

4
1 2 1

1

7
1 2 3 2 4 2

2

15
1 1 1 3 1 5 4 3 1 4 9 4 5 4

2