Problem : 293 - Graph Reconstruction

Special Judge

Problem Statistics

Solved Member: 18　　Submission: 121　　User Tried: 19

Statement:

給定一張簡單無向圖，點編號為 1 至 n ，且每個點的度數不超過2，對於任意點對，最多只會有一條邊相連，且沒有自己連自己的邊。

現在你要構造一張新的圖，並滿足以下條件：

　　• 新圖的點數與邊數與原圖一樣多。
　　• 必須滿足第一段所敘述的條件。
　　• 原圖所出現的邊，新圖不能出現。

Input:Output:

第一行有兩個數字 n m (1 ≤ m ≤ n ≤ 10⁵)，接下來有m行，每行兩個數字u v，表示點u與點v有一條連邊。

如果沒有解輸出-1，否則輸出恰好 m 行，表示新圖的 m 條邊。

若有多組解，輸出任意一組即可。

Sample Input:Sample Output:

Sample #1:
8 7
1 2
2 3
4 5
5 6
6 8
8 7
7 4

Sample #2:
3 2
1 2
2 3

Sample #3:
5 4
1 2
2 3
3 4
4 1

Sample #1:
1 4
4 6
1 6
2 7
7 5
8 5
2 8

Sample #2:
-1

Sample #3:
1 3
3 5
5 2
2 4

HINT:

Sample #1:
輸入圖:

輸出圖:

Sample #3:
輸入圖:

輸出圖:

Source:

Codeforces #192

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	2000ms	262144kb
0-2	2000ms	262144kb
0-3	2000ms	262144kb
1-1	2000ms	262144kb	10
1-2	2000ms	262144kb
1-3	2000ms	262144kb
1-4	2000ms	262144kb
1-5	2000ms	262144kb
2-1	2000ms	262144kb	10
2-2	2000ms	262144kb
2-3	2000ms	262144kb
2-4	2000ms	262144kb
2-5	2000ms	262144kb
3-1	2000ms	262144kb	10
3-2	2000ms	262144kb
3-3	2000ms	262144kb
3-4	2000ms	262144kb
3-5	2000ms	262144kb
4-1	2000ms	262144kb	10
4-2	2000ms	262144kb
5-1	2000ms	262144kb	10
5-2	2000ms	262144kb
5-3	2000ms	262144kb
6	2000ms	262144kb	10
7	2000ms	262144kb	10
8-1	2000ms	262144kb	10
8-2	2000ms	262144kb
8-3	2000ms	262144kb
9-1	2000ms	262144kb	10
9-2	2000ms	262144kb
9-3	2000ms	262144kb
9-4	2000ms	262144kb
9-5	2000ms	262144kb
10-1	2000ms	262144kb	10
10-2	2000ms	262144kb
10-3	2000ms	262144kb
10-4	2000ms	262144kb
10-5	2000ms	262144kb