AT_abc394_f [ABC394F] Alkane

$ N $ 頂点の無向木 $ T $ が与えられます。頂点には $ 1, 2, \ldots, N $ の番号が付いており、 $ i $ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結ぶ無向辺です。 グラフが**アルカン**であるとは以下の条件をともに満たしていることであると定義します。 - グラフは無向木である - すべての頂点の次数が $ 1 $ または $ 4 $ であり、次数 $ 4 $ の頂点が $ 1 $ つ以上存在する $ T $ の部分グラフであってアルカンであるものが存在するか判定し、存在する場合はそのようなものの頂点数の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_{N - 1} $ $ B_{N - 1} $

$ T $ の部分グラフであってアルカンであるものが存在する場合はそのようなものの頂点数の最大値を出力せよ。そうでない場合は $ -1 $ と出力せよ。

### Sample Explanation 1 頂点 $ u $ と頂点 $ v $ を結ぶ無向辺を辺 $ (u, v) $ と表記します。 頂点 $ 1,2,3,4,6,7,8,9 $ 、辺 $ (1,2),(2,3),(3,4),(2,6),(2,7),(3,8),(3,9) $ からなる部分グラフはアルカンです。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq A_i, B_i \leq N $ - 与えられるグラフは無向木 - 入力される値はすべて整数