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

Sample Output 1

3 1
1 3 5
3

Sample Input 2

Sample Output 2

3 1
2 3 5
3

Sample Input 3

Sample Output 3

2 2
2 4
1 4

Hints

Problem Source

IOICamp 2024 Day3 pG

No.	Testdata Range	Constraints	Score
1	0~2	範例測資	0
2	0~11	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	262144	65536	1 2
1	1000	262144	65536	1 2
2	1000	262144	65536	1 2
3	1000	262144	65536	2
4	1000	262144	65536	2
5	1000	262144	65536	2
6	1000	262144	65536	2
7	1000	262144	65536	2
8	1000	262144	65536	2
9	1000	262144	65536	2
10	1000	262144	65536	2
11	1000	262144	65536	2

32 . 奇異果打牌

TopCoder

User's AC Ratio

Submission's AC Ratio

Tags

Description

Input Format

Output Format

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Hints

Problem Source

Subtasks

Testdata and Limits

32 . 奇異果打牌

TopCoder

User's AC Ratio

Submission's AC Ratio

Tags Show solution-related tags

Description

Input Format

Output Format

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Hints

Problem Source

Subtasks

Testdata and Limits

Tags