题目描述

宇宙中有 $N$ 颗行星，Google 的空间部门安装了 $N$ 条真空管道，你可以通过这些管道在行星之间旅行。管道是双向的，旅行者可以使用连接两颗行星的管道从其中一颗行星前往另一颗。每条真空管道连接两颗行星，且没有两条管道连接同一对行星。这些管道将行星连接起来，使得从任意一颗行星出发，可以沿一条或多条管道到达任意其他行星。其中一些管道的连接方式使得宇宙中恰好存在一个环。Google 将礼物藏在了这个环上的所有行星中。现在，Google 想知道宇宙中每颗行星距离这些礼物有多远。

你的任务是求出每颗行星到环上某颗行星的最短距离（以真空管道的数量计）。环上的行星距离视为 $0$。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$，表示行星和真空管道的数量。行星编号为 $1$ 到 $N$。

接下来 $N$ 行，其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 条真空管道连接行星 $x_i$ 和行星 $y_i$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是一个包含 $N$ 个空格分隔的值的列表，其中第 $i$ 个值表示第 $i$ 颗行星到环上某颗行星的最短距离。

2
5
1 2
2 3
3 4
2 4
5 3
3
1 2
3 2
1 3

Case #1: 1 0 0 0 1
Case #2: 0 0 0

提示

在样例 #1 中，环由行星 $2$、$3$ 和 $4$ 组成。因此，行星 $2$、$3$ 和 $4$ 的距离为 $0$。行星 $1$ 与 $2$ 之间有管道，行星 $3$ 与 $5$ 之间也有管道。因此，行星 $1$ 和 $5$ 到环的距离为 $1$。

在样例 #2 中，所有行星都属于环，因此它们的距离均为 $0$。

限制条件

$1 \le T \le 100$。

对于所有 $i$，$1 \le x_i \le N$。

对于所有 $i$，$1 \le y_i \le N$。

对于所有 $i$，$x_i \neq y_i$。

对于所有 $i \neq j$，$(x_i, y_i) \neq (x_j, y_j)$。

以行星为节点、管道为边的图是连通的，并且恰好包含一个环。

小数据集（测试集 1 – 可见）

$3 \le N \le 30$。

大数据集（测试集 2 – 隐藏）

$3 \le N \le 1000$。

翻译由 DeepSeek V4 Pro 完成