TopCoder

WeaK
weak.infor.org 雖然這裡好像沒什麼東西。

User's AC Ratio

86.4% (19/22)

Submission's AC Ratio

20.7% (34/164)

Description

你是一間航空公司的老闆,你的航空公司在 n 個城市間架有 k 條航線。

現在你想將所有的航線從 1~k 編號,但是你又不想很無趣的按照順序編號。

所以你就想到了一個好方法,就是你希望將所有航線編號,使得每個城市連出的所有航線,編號的最大公因數都是 1。

但是如果某個城市只連出一條以下的航線,那我們就不對這個城市做任何的要求。

請問你的願望有沒有可能達成呢?但因為編號方法可能有很多種,所以這題採用互動式方式。

在程式碼的最上端,請引入 "lib1481.h"該標頭檔。

* void Init():在進行任何事情之前,請先呼叫這個函數進行初始化。

* void Possible():如果有可能達成請呼叫 Possible()。

* void Impossible():如果不可能達成請呼叫 Impossible()。

* void Number(int X):如果呼叫 Possible() 後,第 i 次呼叫 Number(X) 表示第 i 條邊的編號是 X。

* void Finish():結束編號。

Input Format

本題只有一筆測試資料。

第一行有兩個正整數n, k,表示有 n 個城市和 k 條航線 ( 1 <= n <=2000 , 0 <= k <=20000 )。

接下來有 k 行,第 i 行會有兩個正整數 st, ed,表示第 i 條航線連接第 st 個城市和第 ed 個城市之間。
( 1 <= st, ed <= n )

我們保證任兩個城市之間,一定有辦法透過許多航線而連接。

Output Format

請先呼叫Possible()或是Impossible(),表示有沒有可能達成符合要求的編號。

如果有可能的話,請依照輸入順序依序呼叫 Number() 表示各邊的編號。

最後請呼叫Finish(),表示結束。

Sample Input

6 6
1 2
2 3
2 4
4 3
5 6
4 5

Sample Output

其中一種可能的方法:
Init();
Possible();
Number(4);
Number(2);
Number(3);
Number(1);
Number(5);
Number(6);
Finish();

Hints

Problem Source

原TIOJ1481 / 建中校內培訓第六次模擬考試。
Problem Setter:hallogameboy、peter50216
Adapt From:Ural UIC Oct'00

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536