你负责 BubbleReactor。它由 $$$N$$$ BubbleCore 与 $$$N$$$ 电线连接而成。每条电线连接两个不同的 BubbleCore。没有 BubbleCore 与多于一根电线连接。
您的任务是通过启动每个 BubbleCore 来启动 BubbleReactor。为了启动 BubbleCore,它需要从已启动的直接连接的 BubbleCore 接收电力。不过,您可以手动启动一个 BubbleCore,无需电源。保证所有BubbleCore都能启动。
在 BubbleCore 启动过程之前,其潜力被计算为它可以启动的 BubbleCore 数量(直接连接到它的不活动 BubbleCore 的数量或之间任意数量的不活动 BubbleCore 的数量,包括其本身)
启动 BubbleReactor,使所有 BubbleCore 的电势之和最大。
输入
第一行包含一个整数 $$$N (3 \leq N \leq 15.000)$$$,BubbleCore 的数量。
接下来的 N 行包含两个整数 $$$U, V (0 \leq U \neq V < N)$$$ 表示 BubbleCore $$$U$$$ 和 $$$V$$$ 之间存在电线。
输出
单个整数,所有 BubbleCore 潜力的最大总和。
示例
输入 #1
10 0 1 0 3 0 4 0 9 1 2 2 3 2 7 4 5 4 6 7 8
输出 #1
51
注意
如果我们首先启动 BubbleCup 8,然后按顺序打开核心 7、2、1、3、0、9、4、5、6,我们将得到电位 10 + 9 + 8 + 7 + 6 + 5 + 1 + 3 + 1 + 1 = 51