你是一間航空公司的老闆,你的航空公司在 $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()
:結束編號。本題只有一筆測試資料。
第一行有兩個正整數 $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$)
我們保證任兩個城市之間,一定有辦法透過許多航線而連接。
請先呼叫 Possible()
或是 Impossible()
,表示有沒有可能達成符合要求的編號。
如果有可能的話,請依照輸入順序依序呼叫 Number()
表示各邊的編號。
最後請呼叫 Finish()
,表示結束。
原TIOJ1481 / 建中校內培訓第六次模擬考試。
Problem Setter:hallogameboy、peter50216
Adapt From:Ural UIC Oct'00
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 |