题目描述

有 $n$ 隻貓活動於某個地區，每隻貓各有其棲息地，編號為 $1$ 到 $n$。棲息地之間有 $m$ 條道路連接，道路總數不超過 $2n-4$。第 $i$ 條道路連接第 $a_i$ 個棲息地和第 $b_i$ 個棲息地，貓可以沿著這些道路在棲息地之間雙向移動，且不會有兩條不同的道路連接著同一對棲息地。有 $3$ 個動保團體要接管此地區，請你協助將這 $n$ 個棲息地分配給這 $3$ 個團體，滿足以下要求：

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

舉例，有 $5$ 個棲息地，道路連接如下圖所示

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