TopCoder

Thumb screenshot 2020 12 08 170353
自動姬
我要把自己丟進垃圾桶, 再把蓋子蓋起來

User's AC Ratio

84.6% (55/65)

Submission's AC Ratio

18.8% (108/574)

Description

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

現在你想將所有的航線從 $1 \sim 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 \le n \le 2000 , 0 \le k \le 20000$)。

接下來有 $k$ 行,第 $i$ 行會有兩個正整數 $st, ed$,表示第 $i$ 條航線連接第 $st$ 個城市和第 $ed$ 個城市之間。
($1 \le st, ed \le 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

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 (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