g727: 蝸牛老師的冰棒
Tags : dfs dsu
Accepted rate : 13人/17人 ( 76% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-11-29 20:59

Content

臨末之頌最喜歡偷吃蝸牛老師的冰棒了,有一天,蝸牛老師發現後決定要懲罰他。

蝸牛老師決定在臨末之頌面前請k個學生吃冰棒,於是吩咐臨末之頌把他的冰棒都拿出來。

蝸牛老師總共有n種口味的冰棒,用整數1,2,...,n編號,每種口味各一個。而每個學生都恰好有兩種喜歡的口味,吃冰棒的流程如下:

  • 首先,臨末之頌會以某種方式為學生們排好隊。
  • 按照這個順序,學生們會一一來吃冰棒。
  • 每位學生輪到他時,將會吃掉他喜歡的口味的所有剩餘的冰棒。
  • 如果輪到某個學生時沒有他喜歡的口味了,他會變得非常難過。

為了起到懲罰的作用,蝸牛老師要求他以最佳方式排列學生們,使得最多數量的學生可以吃到冰棒。

由於臨末之頌自己吃不到冰棒,於是他就好奇了有多少人跟他一樣也吃不到冰棒。

Input

第一行包含兩個整數nk(2≤n≤10^5,1≤k≤10^5),代表冰棒數和學生數。

接下來有k行,每行包含兩個整數xiyi(1≤xi,yi≤n,xi≠yi),表示第i個學生喜歡的兩種冰棒口味。

Output

請輸出一個整數,代表經過最好的排列後,最少有多少學生跟臨末之頌一樣吃不到冰棒。

Sample Input #1
5 4
1 2
4 3
1 4
3 4
Sample Output #1
1
Sample Input #2
6 5
2 3
2 1
3 4
6 5
4 5
Sample Output #2
0
測資資訊:
記憶體限制: 128 MB
公開 測資點#0 (5%): 1.0s , <1M
公開 測資點#1 (5%): 1.0s , <1M
公開 測資點#2 (5%): 1.0s , <1M
公開 測資點#3 (5%): 1.0s , <1M
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <10M
公開 測資點#11 (5%): 1.0s , <10M
公開 測資點#12 (5%): 1.0s , <10M
公開 測資點#13 (5%): 1.0s , <10M
公開 測資點#14 (5%): 1.0s , <10M
公開 測資點#15 (5%): 1.0s , <10M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <10M
Hint :

範例說明一:

存在最好的排列可以使:
第一位學生吃口味1、2的冰棒
第二位學生吃口味3的冰棒
第三位學生吃口味4的冰棒
第四位學生吃不到冰棒

範例說明二:

存在最好的排列可以使:
第一位學生吃口味3的冰棒
第二位學生吃口味1、2的冰棒
第三位學生吃口味4的冰棒
第四位學生吃口味6的冰棒
第五位學生吃口味5的冰棒

Tags:
dfs dsu
出處:
蝸牛與臨末之頌 [管理者: Ststone1687(使用C++的都邪教) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」