TopCoder

Thumb a
$ $
$ \color{red}{\href{../users/icube}{\circ Inactive}} $

User's AC Ratio

79.5% (31/39)

Submission's AC Ratio

38.0% (46/121)

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)
0 900 524288
1 900 524288
2 900 524288
3 900 524288
4 900 524288
5 900 524288
6 900 524288
7 900 524288
8 900 524288
9 900 524288
10 900 524288
11 900 524288
12 900 524288
13 900 524288
14 900 524288
15 900 524288
16 900 524288
17 900 524288
18 900 524288
19 900 524288
20 900 524288
21 900 524288
22 900 524288
23 900 524288
24 900 524288
25 900 524288
26 900 524288
27 900 524288
28 1900 524288
29 1900 524288
30 1900 524288
31 1900 524288
32 1900 524288
33 1900 524288
34 1900 524288
35 1900 524288
36 1900 524288
37 1900 524288
38 1900 524288
39 1900 524288
40 1900 524288
41 1900 524288
42 1900 524288
43 2900 524288
44 2900 524288
45 2900 524288
46 2900 524288
47 2900 524288
48 2900 524288
49 2900 524288
50 2900 524288
51 2900 524288
52 2900 524288
53 2900 524288
54 2900 524288
55 2900 524288
56 2900 524288
57 2900 524288
58 2900 524288
59 2900 524288