題目 2439:
信息學(xué)奧賽一本通T1533-相框
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 4 解決: 3
題目描述
原題來自：福建集訓(xùn) 2011
P 大的基礎(chǔ)電路實(shí)驗(yàn)課是一個(gè)無聊至極的課。每次實(shí)驗(yàn)，T 君總是提前完成，管理員卻不讓 T 君離開，T 君只能干坐在那兒無所事事。
先說說這個(gè)實(shí)驗(yàn)課，無非就是把幾根導(dǎo)線和某些元器件（電阻、電容、電感等）用焊錫焊接起來。
為了打發(fā)時(shí)間，T 君每次實(shí)驗(yàn)做完后都在焊接一些詭異的東西，這就是他的杰作：
T 君不滿足于焊接奇形怪狀的作品，強(qiáng)烈的破壞欲驅(qū)使他拆掉這個(gè)作品，然后將之焊接成規(guī)整的形狀。這會(huì)兒，T 君正要把這個(gè)怪物改造成一個(gè)環(huán)形，當(dāng)作自己的相框，步驟如下：
T 君約定了兩種操作：
燒熔一個(gè)焊點(diǎn)：使得連接在焊點(diǎn)上的某些導(dǎo)線相分離或保持相連（可以理解為：把焊點(diǎn)上的導(dǎo)線劃分為若干個(gè)類，相同類中的導(dǎo)線相連，不同類之間的導(dǎo)線相離）
將兩根導(dǎo)線的自由端（即未與任何導(dǎo)線相連的一端）焊接起來。
例如上面的步驟中，先將 A 點(diǎn)燒熔，使得導(dǎo)線 1 與導(dǎo)線 2,4 點(diǎn)分離；再將 D 點(diǎn)燒熔，使得 4,5 與 3,7相離；再燒熔 E，使 7 與 6,8 相離；最后將 1,7 相連。
T 君想用最少的操作來將原有的作品改造成為相框（要用上所有的導(dǎo)線）。
輸入格式
第一行共有兩個(gè)整數(shù) n 和 m——分別表示原有的作品的焊點(diǎn)和導(dǎo)線的數(shù)量。焊點(diǎn)的標(biāo)號(hào)為 1～n。 接下來的 m 行每行共有兩個(gè)整數(shù)——導(dǎo)線兩端所連接的兩個(gè)焊點(diǎn)的標(biāo)號(hào)，若不與任何焊點(diǎn)相連，則將這一端標(biāo)號(hào)為 0。
原有的作品可能不是連通的。
某些焊點(diǎn)可能只有一根導(dǎo)線與之相連，在該導(dǎo)線的這一端與其他導(dǎo)線相連之前，這些焊點(diǎn)不允許被燒熔。
某些焊點(diǎn)甚至沒有任何導(dǎo)線與之相連，由于 T 君只關(guān)心導(dǎo)線，因此這些焊點(diǎn)可以不被考慮。
原有的作品可能不是連通的。
某些焊點(diǎn)可能只有一根導(dǎo)線與之相連，在該導(dǎo)線的這一端與其他導(dǎo)線相連之前，這些焊點(diǎn)不允許被燒熔。
某些焊點(diǎn)甚至沒有任何導(dǎo)線與之相連，由于 T 君只關(guān)心導(dǎo)線，因此這些焊點(diǎn)可以不被考慮。
輸出格式
只包含一個(gè)整數(shù)——表示 T 君需要將原有的作品改造成相框的最少步數(shù)。
樣例輸入
6 8 1 2 1 3 3 4 1 4 4 6 5 6 4 5 1 5
樣例輸出
4
提示
數(shù)據(jù)范圍與提示：
30% 的數(shù)據(jù)中 n≤10；
100% 的數(shù)據(jù)中0≤n≤1000,2≤m≤50000。
30% 的數(shù)據(jù)中 n≤10；
100% 的數(shù)據(jù)中0≤n≤1000,2≤m≤50000。