a270. TOI 2023/04 潛力組：破冰活動

題目描述

N 位社員中，有 M 對彼此認識的人。要將所有社員分成兩隊，且同一隊內不能有任何一對互相認識的人。隊伍不要求人數相同。

若能分隊，請計算所有合法分隊方式中，較大隊伍的人數最大可以是多少。若完全無法分成符合條件的兩隊，答案為 0。

輸入格式

第一行為 N、M，接著 M 行各有 A、B，表示這兩位社員互相認識。

• 3 ≤ N ≤ 10000
• 1 ≤ M ≤ min(N(N−1)/2,100000)
• 1 ≤ A < B ≤ N
• 沒有重複的關係。

輸出格式

輸出所求的最大隊伍人數，無法分隊時輸出 0。

來源

TOI 2023 年 4 月潛力組〈破冰活動〉。以自寫文字重述，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202304/Icebreaker.pdf 題意核對鏡像：https://zerojudge.tw/ShowProblem?problemid=k463