45. 交通工具 2

0 Judge

Code: 0


交通工具 2

題目敘述

海牛最近想買車,可是海牛國很大,而且有很多城市,他怕車子開到一半可能會沒油,所以他希望可以買足夠油量的車,讓他可以從任兩個城市間移動而不會沒油。

跟上次不同,海牛國的城市間建起了道路,道路連接兩個城市,長度都是一,為了節省成本,海牛國只建了城市數減一的道路,任兩城市之間必定有路徑,這次請告訴他最遠兩個城市的最短路徑。

輸入說明

第一行有一個$T(T \leq 10)$,代表測資數。 接下來每筆測資,第一行有一個N,代表城市數, 接下來$N - 1$行,每行有2個整數$u, v$,代表兩個端點,$1 \leq u, v \leq N$。

輸出說明

對於每筆測資,輸出一行最遠距離。

範例輸入

範例輸出

子題一[30%]

$2 \leq N \leq 100$

子題二[40%]

$2 \leq N \leq 10000$

子題三[30%]

$2 \leq N \leq 100000$


Judge Setting

run-time limit: 1000 ms
memory limit: 104857600 byte
測資數量: 3