SP9126 GCPC11J - Time to live

你可能知道，大多数的计算机网络是树状结构，这意味着每台计算机之间可以通过唯一的路径互相连接。 「生存时间」（TTL）指的是网络数据包在传输时，若未到达目的地，会在经过一定次数的跳转后被丢弃。设置 TTL 的目的是避免因路由表错误导致数据包在网络中无限循环。 当一个连接网络到其他网络的路由器放置在最优位置时，从该路由器发出到同一网络内任意其他计算机的数据包，所需的最大 TTL 应尽可能小。给定这样的网络配置，你的任务是计算出当选择任意一台计算机作为路由器时，所需的最小最大 TTL。

第一行输入一个整数 $c$，表示测试用例的数量（$1 \le c \le 100$）。每个测试用例的第一行包含一个整数 $N$，表示网络中的计算机数量（$1 < N \le 1000$）。接下来有 $N-1$ 行，每行包含两个整数 $a$ 和 $b$，表示计算机 $a$ 和 $b$ 之间有直接连接（$0 \le a, b < N$）。

对于每个测试用例，输出一个整数，表示最优条件下的最大 TTL。 **本翻译由 AI 自动生成**