a145. TOI 2024/09 潛力組：校外教學分組

題目描述

要將 N 位學生分成三組，每位學生恰屬於一組。給定學生之間的朋友關係，同一組中不可以有任何一對朋友。

在符合條件的分組方式中，請讓人數最多的一組與人數最少的一組之差盡量小，並輸出這個最小差值。若沒有任何符合朋友限制的分組方式，輸出 -1。

輸入格式

第一行輸入 N、M，3 ≤ N ≤ 16，1 ≤ M ≤ N(N−1)/2。 接下來 M 行各輸入 X、Y，表示編號 X 與 Y 的學生是朋友，其中 1 ≤ X、Y ≤ N 且 X ≠ Y。 每對朋友關係只會出現一次。

輸出格式

輸出三組人數最大值與最小值之差的最小可能值；無法分組時輸出 -1。

來源

TOI 2024 年 9 月潛力組〈校外教學分組〉。依官方題意重新撰寫，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202410/trip.pdf