TopCoder

User's AC Ratio

85.5% (65/76)

Submission's AC Ratio

18.5% (136/736)

Tags

Description

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

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

所以你就想到了一個好方法,就是你希望將所有航線編號,使得每個城市連出的所有航線,編號的最大公因數都是 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 條航線(1n2000,0k20000)。

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

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

Output Format

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

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

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

Sample Input 1

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

Sample Output 1

其中一種可能的方法:
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

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10
10 1000 65536 262144 11