骨幹網路是網際網路中重要的基礎設施。骨幹網路由多台伺服器組成，彼此間以高速網路連結；其他電腦與裝置，則透過骨幹網路連線到網際網路上。機關、學校、公司與資料中心也經常透過建置自己的骨幹網路，來提供內部與外部的網路服務。

骨幹網路中的伺服器通常透過不只一條的實體連線相互連結，提供妥善的分流與備援。確保每條連線的品質，就是確保骨幹網路穩定的基本方法，然而有效率的測試所有連線可能是相當艱鉅的任務。假設每條直接連線都是雙向的，考慮以下的簡單方法：「每台伺服器都有自己的唯一 ID 識別碼。每台伺服器查看所有與自己直接連線的伺服器 ID，如對方的 ID 比自己的 ID 大，則 ID 較小的伺服器負責對此連線進行測試。」

如此一來，每條直接連線都會被測試恰好一次。然而 ID 較小又擁有較多直接連線的伺服器可能得負擔較多的測試，會導致測試工作的分配並不是很平均。我們能靠重新分配伺服器的 ID，以減少(最小化)伺服器最大的負擔。例如以下這張網路：

需要的測試如下：

伺服器 0 → {1, 4, 5}
伺服器 1 → {2, 5}
伺服器 2 → {3, 5}
伺服器 3 → {4}
伺服器 4 → {5,6}
伺服器 5 → {}
伺服器 6 → {}

伺服器 0 最多需要 3 次測試。 

若 ID 經過適當地重新分配後：

需要的測試如下：

伺服器 0 → {4}
伺服器 1 → {2, 4}
伺服器 2 → {3, 5}
伺服器 3 → {5, 6}
伺服器 4 → {5,6}
伺服器 5 → {6}
伺服器 6 → {}

伺服器 1,2,3,4 最多只需要 2 次測試。 

可見適當的重新分配 ID，可以使最多的連線測試次數減少。對於給定的網路關係圖，請問重新分配 ID 後，每台伺服器最多連線測試次數可以減至多少? 

輸入第一行為一個整數 T (T <= 10)，以下包含 T 組測資。

每組測資的第一行有以空白分隔的兩個整數 N (N<=500,000)與 E (E<=800,000)；N 是伺服器的數量，E 表示直接連線的數量。

往後有 E 行。每行包含以空白分隔的兩個整數 u 與 v (0 <= u,v < N)，表示伺服器 u 與 v 之間有直接連線。任一伺服器不會直接連線到自己，任兩伺服器間不會出現重複的連線，但不保證任兩伺服器之間有連通。 

1
7 10
4 6
4 0
4 5
4 3
5 0
5 1
5 2
3 2
1 0
1 2

3 2