P13408 [GCJ 2010 Finals] City Tour

在夏季，欧洲的老城市里到处都是游客，他们在街道上漫步，参观各种景点。 许多老城市并不是按照某种建筑规划而建造的，而是自然生长的，但奇怪的是，它们的扩展却表现出类似的模式：城市最初有三个景点，每一对景点之间都有一条双向街道相连；随后，新的景点逐渐被添加。每添加一个新的景点时，它会通过两条新的双向街道与已经直接相连的两个不同的旧景点相连。 一位游客想要在这样的城市中进行一次游览，尽可能多地参观不同的景点。游览可以从任意一个景点开始，并且必须在同一个景点结束。每条街道最多只能经过一次，每个景点最多只能访问一次（起点景点除外，必须恰好访问两次）。 你将获得该城市扩展的描述。请找出在该城市中一次游览最多可以参观多少个不同的景点。

输入文件的第一行包含测试用例数 $T$。接下来有 $T$ 组测试数据。 每组测试数据以一个整数 $N$ 开头，表示城市中的景点总数。景点编号为 $1$ 到 $N$；编号 $1$、$2$ 和 $3$ 表示城市最初的三个景点，编号 $4$ 到 $N$ 表示后续依次添加的景点。 接下来的 $N-3$ 行，每行包含两个用空格分隔的整数 $A$ 和 $B$，表示相应的景点通过街道与景点 $A$ 和 $B$ 相连。这些行的第 $i$ 行对应编号为 $i+3$ 的景点。

对于每个测试用例，输出一行，格式为 “Case #$x$: $y$”，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是一次游览最多可以参观的不同景点数。

**数据范围** - $1 \leq T \leq 50$。 **小数据范围（4 分，测试点 1 - 可见）** - $4 \leq N \leq 15$。 **大数据范围（23 分，测试点 2 - 隐藏）** - $4 \leq N \leq 1000$。 由 ChatGPT 4.1 翻译