給定一張無向圖$G = \{V,E\}$,點由1編號到$N$,請找出兩個不相交點集$S,T$(即$S,T$沒有共同點),使得$S,T$都是$G$的邊覆蓋。
若$S$是一張圖$G$點集的子集,且圖中每一條邊都至少接觸$S$中的一個頂點,即稱$S$是$G$的邊覆蓋。
第一行有兩個非負整數$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)$,且給定的圖是簡單圖(沒有自環或重邊)。
第一行輸出兩個數字,分別代表點集$S$跟$T$的大小,
第二行輸出點集$S$的元素,第三行輸出點集$T$的元素。
如果無法找到,輸出-1
。
注意:由於本題輸入/輸出十分龐大,使用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 set by edisonhello
建國中學107學年度校隊選拔:複試pA
No. | Testdata Range | Constraints | Score |
---|---|---|---|
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 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
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 |