statement.md

島と橋

Problem Statements

カズー氏は群島国家「サカモ島国」の管理者である。この国には、V個の島(1からVまでの番号で管理されている)と、2つの異なる島をつなぐE個の橋がある。 島Xから島Yにいくつかの橋を通って移動できるとき、XとYは「相互移動可能」と呼ぶことにする。

カズー氏は、交通インフラの整備をするため、もともと船で行き来をしていた島同士に新しくいくつかの橋をかけ、V個の島全てのペアについて、「相互移動可能」にすることにした。 目的達成のために、新しい橋は少なくともいくつ必要か求めよ。 ただし、全ての島のペアについて既に「相互移動可能」である状態ならば、0 を出力せよ。

Input

入力は以下の形式で表される。

D
V₁ E₁
S₁₁ G₁₁
S₁₂ G₁₂
:
S_1E1 G_1E1
V₂ E₂
S₂₁ G₂₁
S₂₂ G₂₂
:
S_2E2 G_2E2
:
V_D E_D
S_D1 G_D1
S_D2 G_D2
:
S_DED G_DED

ここでDはデータセットの個数である。また、i番目のデータセットにおいて、V_iは島の数、E_iは橋の数、S_ijおよびG_ijはj番目の橋がつないでいる島の番号である。

Constraints

入力は、以下の条件をすべて満たす。

• 1 <= D <= 100
• 1 <= i <= D を満たすすべての整数iについて、
  • 2 <= V_i <= 1000
  • 0 <= E_i <= 1000
  • さらに、 1 <= j <= E_i を満たすすべての整数jについて、
    • 1 <= S_ij <= V_i
    • 1 <= G_ij <= V_i
    • S_ij != G_ij

Sample Input

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

Sample Output

2
0
2