User's AC Ratio

81.8% (36/44)

Submission's AC Ratio

38.8% (52/134)

Description

給定一張無向圖$G = \{V,E\}$,點由1編號到$N$,請找出兩個不相交點集$S,T$(即$S,T$沒有共同點),使得$S,T$都是$G$的邊覆蓋。
若$S$是一張圖$G$點集的子集,且圖中每一條邊都至少接觸$S$中的一個頂點,即稱$S$是$G$的邊覆蓋。

Input Format

第一行有兩個非負整數$N,M$,代表點數與邊數。
接下來的$M$行各代表圖上的一條邊,每行各有兩個正整數$u,v$代表該邊連接的頂點編號。

對於所有測資,$1 \leq N\leq 10^ 6; M \leq \min\left( \frac{N(N-1)}{2}, 2\times 10^ 6\right)$,且給定的圖是簡單圖(沒有自環或重邊)。

子任務(測資) 額外限制 分數
1 (0~17) $N \leq 10$ 9
2 (0~27) $N \leq 20$ 13
3 (0~42) $N \leq 3000$ 29
4 (0~59) 無額外限制 49

Output Format

第一行輸出兩個數字,分別代表點集$S$跟$T$的大小,
第二行輸出點集$S$的元素,第三行輸出點集$T$的元素。
如果無法找到,輸出-1

Sample Input

2 1
1 2

Sample Output

1 1
1
2

Hints

注意:由於本題輸入/輸出十分龐大,使用C++作答的同學,請在程式碼開頭加上#include <cstdio>,並利用scanf讀入資料、用printf輸出資料

scanf 常用的讀入方式如下:
scanf("%d",&x); 讀入一個有號整數至int 型態變數x。
scanf("%lld",&y); 讀入一個有號整數至long long 型態變數y。

printf 常用的輸出方式如下:
printf("%d\n",x); 輸出一行包含一個int 型態變數x。
printf("%lld\n",y); 輸出一行包含一個long long 型態變數y。

Problem Source

Problem set by edisonhello
建國中學107學年度校隊選拔:複試pA

Subtasks

For Testdata: 0 ~ 17, Score: 9
For Testdata: 0 ~ 27, Score: 13
For Testdata: 0 ~ 42, Score: 29
For Testdata: 0 ~ 59, Score: 49
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 900 524288 262144
1 900 524288 262144
2 900 524288 262144
3 900 524288 262144
4 900 524288 262144
5 900 524288 262144
6 900 524288 262144
7 900 524288 262144
8 900 524288 262144
9 900 524288 262144
10 900 524288 262144
11 900 524288 262144
12 900 524288 262144
13 900 524288 262144
14 900 524288 262144
15 900 524288 262144
16 900 524288 262144
17 900 524288 262144
18 900 524288 262144
19 900 524288 262144
20 900 524288 262144
21 900 524288 262144
22 900 524288 262144
23 900 524288 262144
24 900 524288 262144
25 900 524288 262144
26 900 524288 262144
27 900 524288 262144
28 1900 524288 262144
29 1900 524288 262144
30 1900 524288 262144
31 1900 524288 262144
32 1900 524288 262144
33 1900 524288 262144
34 1900 524288 262144
35 1900 524288 262144
36 1900 524288 262144
37 1900 524288 262144
38 1900 524288 262144
39 1900 524288 262144
40 1900 524288 262144
41 1900 524288 262144
42 1900 524288 262144
43 2900 524288 262144
44 2900 524288 262144
45 2900 524288 262144
46 2900 524288 262144
47 2900 524288 262144
48 2900 524288 262144
49 2900 524288 262144
50 2900 524288 262144
51 2900 524288 262144
52 2900 524288 262144
53 2900 524288 262144
54 2900 524288 262144
55 2900 524288 262144
56 2900 524288 262144
57 2900 524288 262144
58 2900 524288 262144
59 2900 524288 262144