TopCoder

User's AC Ratio

62.5% (5/8)

Submission's AC Ratio

13.5% (10/74)

Description

還記得海鞘嗎?對,就是上次那隻視財如命的烏龜。
海鞘的藏寶窟群越蓋越大,到最後已經由原本的樹狀變成複雜的網狀結構。

他的藏寶窟群由V個藏寶窟組成、雙向連通的通道則有E條。
他希望安排一些守衛來巡邏每條道路。巡邏的龜則是這樣的:

每隻警衛會被安排一條巡邏路徑,每天早上三點會從路徑起點端巡邏到終點端、下午三點會從終點端回到起點。
海鞘希望每條通道都會恰好被巡邏到一次。

海鞘是數學一哥,他知道奇點有0個或2個時只需要一位警衛,超過2就不行了。
但是他也是節儉一哥,他希望僱用最少位警衛達成巡邏所有通道的任務。

海鞘找到了你,假設你幫他安排一組巡邏方案他就會給你109枚烏龜幣作為報酬。

本題不需進行輸入輸出,請先引入#include "lib1692.h"並使用以下函式完成任務:

*void Init(void);
在你作任何操作前請先呼叫這個函式。

*void GetVE(int&V, int&E);
只能呼叫一次,V表示藏寶窟的數量、E表示通道的數量。

*void Get(int&V1, int&V2);
能呼叫E次,第i次呼叫代表通道i是連接V1和V2。

*void ReportVst(int st);
*void ReportVed(int ed);
*void ReportE(int n);

用來回報一條路徑依序經過的通道編號。例如有一條1→2→4→2→5的巡邏路徑,
而通道1連接1和2、通道2連接4和2、通道3連接2和5、通道4連接2和4,
那麼你可以這樣回報:
ReportVst(1);  //代表巡邏起點為房間1
ReportE(1);    //代表走過通道1,走到房間2
ReportE(2);    //代表走過通道2,走到房間4
ReportE(4);    //代表走過通道4,走到房間2
ReportE(3);    //代表走過通道3,走到房間5
ReportVed(5);  //代表巡邏結束在房間5

*void Final(void);
表示已經輸出所有路徑,並會幫你結束程式。

Input Format

本題無須輸入,請依序使用Init()、GetVE()、E次Get()來讀取藏寶窟的資訊。

保證V ≤ 1,000,E ≤ 50,000

Output Format

本題無須輸出,請依照上述方法連續輸出所有人的巡邏路徑。

Sample Input

Sample Output

Hints

你可以在這裡載到一個測試用的.h檔。

例如對於以下藏寶窟結構:
5 4    //代表V=5,E=4,以下E行為編號1~4的通道兩端房間編號。
1 2
1 2
3 5
1 4

以下會是一個能通過此筆測試的程式碼:

#include <cstdio>
#include "lib1692.h"
int edge[50010][2], V, E;
int main() {
    Init();
    GetVE(V, E);
    for(int i=0; i<E; i++) Get(edge[i][0], edge[i][1]);
    ReportVst(1);
    ReportE(1);
    ReportE(2);
    ReportE(4);
    ReportVed(4);
    ReportVst(3);
    ReportE(3);
    ReportVed(5);
    Final();
}

(*)詳情見建國中學2010年校內模擬賽Contest 4 prob 1 / Contest 7 prob 2

Problem Source

原TIOJ1692 / ABCLS Contest, Problem B

Subtasks

For Testdata: 0 ~ 0, Score: 16
For Testdata: 1 ~ 1, Score: 16
For Testdata: 2 ~ 2, Score: 16
For Testdata: 3 ~ 3, Score: 16
For Testdata: 4 ~ 4, Score: 16
For Testdata: 5 ~ 5, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 65536
1 3000 65536 65536
2 3000 65536 65536
3 3000 65536 65536
4 3000 65536 65536
5 3000 65536 65536