問題説明

データセンターにN個のサーバーがあり、サーバー間にネットワーク接続があります。 メインサーバー(1番)から最も遠いサーバーを探します。 距離は最小ホップ数(経由する接続数)で測定します。 1番サーバーから最も遠いサーバーの数を求めてください。

入力

出力

制約条件

• •2 <= N <= 20,000
• •1 <= 辺数 <= 50,000
• •グラフは連結

例

6, [[3,6], [4,3], [3,2], [1,3], [1,2], [2,4], [5,2]]

3