2062 . 分點問題（一）
TopCoder
Tags
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)$，且給定的圖是簡單圖（沒有自環或重邊）。
Output Format
第一行輸出兩個數字，分別代表點集$S$跟$T$的大小，
第二行輸出點集$S$的元素，第三行輸出點集$T$的元素。
如果無法找到，輸出-1。
Sample Input 1
2 1 1 2
Sample Output 1
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
| 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 |