#P11829. [TOIP2024] 棲息地分配

[TOIP2024] 棲息地分配

题目描述

nn 隻貓活動於某個地區,每隻貓各有其棲息地,編號為 11nn。棲息地之間有 mm 條道路連接,道路總數不超過 2n42n-4。第 ii 條道路連接第 aia_i 個棲息地和第 bib_i 個棲息地,貓可以沿著這些道路在棲息地之間雙向移動,且不會有兩條不同的道路連接著同一對棲息地。有 33 個動保團體要接管此地區,請你協助將這 nn 個棲息地分配給這 33 個團體,滿足以下要求:

  • 每個棲息地僅由 11 個團體管理,且每個團體需要管理至少 11 個棲息地。每個團體所屬的棲息地之間不一定要連通。
  • 為了方便管理,每個團體會移除由該團體負責的棲息地之間的道路。換句話說,若有一條道路連接的兩個棲息地被分配到同一個團體,該道路會被移除。
  • 這些道路移除後,剩餘的道路不可以形成「環」,以免貓可能會繞著環奔跑,讓工作人員難以捉捕。也就是說,不可以存在一個兩兩相異的棲息地序列 v1,v2,,vkv_1,v_2,\ldots, v_k​,滿足 k3k \ge 3,且對於所有 1i<k1\le i < k,棲息地 viv_i​ 和棲息地 vi+1v_{i+1}​ 都有一條未被移除的道路連接、同時 vkv_k​ 和 v1v_1​ 也有一條未被移除的道路連接。

舉例,有 55 個棲息地,道路連接如下圖所示

1
5 6
1 2
2 3
3 4
4 5
5 3
4 2
3 3 4 5
1 1
1 2
2
5 4
1 2
1 3
3 4
3 5
5 4
1 2
2 3
1 3
4 5
2 1 2
1 3
2 4 5
3 1 2 3
1 4
1 5