[HOJ 293][Codeforces #192]Graph Reconstruction (題目備份)

HSNU Online Judge

• Index
• User
• Problem
  • Vol.0
  • Vol.1
  • Vol.2
  • Vol.3
  • Vol.4
• Status
• Contest
• Course
• Discuss_Ura

HOJ生病惹QQ，因此在此悼念昔日光彩

題目備份，請參考～

題解在這裡

敬告：目前HOJ主機也許進入瀕死狀態了，常常無預警跳電。請看到這則公告的人能注意備份自己的資料，感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 

Submit　　Ranklist

Problem : 293 - Graph Reconstruction

Special Judge

Problem Statistics

Solved Member: 18　　Submission: 121　　User Tried: 19

Problem：

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

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

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

Input：

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

Output：

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

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

Sample Input：

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 Output：

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

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2652 秒，使用記憶體: 2.87MB 。