32 . 奇異果打牌
TopCoder
Tags
Description
奇異果最喜歡打牌了，他擅打各式各樣的牌，包含各種撲克牌遊戲、麻將、獎牌等等。今天，巴乙己發明了新的紙牌遊戲要來挑戰奇異果，這個遊戲中有 $N$ 張牌，每張牌的正面寫了一個數字，背面畫了一個圖案，數字都是 $1$ 到 $K$ 之間的整數，圖案共有 $K$ 種，第 $i$ 張牌上寫的數字是 $a_i$，畫的圖案是第 $b_i$ 種圖案。奇異果的目標是要選擇一些數字和一些圖案，使得每張牌都滿足上面的數字或圖案至少其中一個被奇異果選中，並且奇異果選中的數字和圖案總數最少，請你告訴奇異果應該要選擇哪些圖案和數字。
Input Format
第一行有兩個正整數 $N,K$。
接下來有 $N$ 行，其中第 $i$ 行有兩個正整數 $a_i,b_i$。
- $1 \leq N \leq 1000$
- $1 \leq K \leq 1000$
- $1 \leq a_i,b_i \leq K$
Output Format
第一行輸出兩個以空白隔開的整數 $A,B$，代表奇異果應該要選擇 $A$ 個數字和 $B$ 個圖案。
第二行輸出 $A$ 個數字 $p_1,p_2,\dots,p_A$，代表奇異果應該要選擇的數字。
第三行輸出 $B$ 個數字 $q_1,q_2,\dots,q_B$，代表奇異果應該要選擇的圖案編號。
你輸出的答案必須滿足以下條件：
- $0 \leq A,B \leq K$
- $1 \leq p_i,q_i \leq K$
- $p_1,p_2,\dots,p_A$ 兩兩相異
- $q_1,q_2,\dots,q_B$ 兩兩相異
- $A+B$ 盡可能小
若有多種可能的解，輸出任意一種，數字和圖案編號可以以任意順序輸出。
Sample Input 1
8 5
1 1
1 2
2 3
3 2
4 3
3 4
5 3
5 5
1 1
1 2
2 3
3 2
4 3
3 4
5 3
5 5
Sample Output 1
3 1
1 3 5
3
1 3 5
3
Sample Input 2
5 5
4 3
3 1
1 3
2 4
5 5
4 3
3 1
1 3
2 4
5 5
Sample Output 2
3 1
2 3 5
3
2 3 5
3
Sample Input 3
10 5
1 4
2 3
2 5
4 4
3 1
4 3
5 4
3 4
4 2
5 1
1 4
2 3
2 5
4 4
3 1
4 3
5 4
3 4
4 2
5 1
Sample Output 3
2 2
2 4
1 4
2 4
1 4
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資。 | 0 |
| 2 | 0~11 | 無特別限制。 | 100 |