回分類題庫
h167: G.普遜與食安問題
關鍵字: NPSC 2016 高中組初賽

測資點 : 4 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 17 Times / 15 Users | Submit : 58 Times / 18 Users | Accepted rate : 83%
題目加入時間 : 2017-11-03 11:50

Content: 简体中文

普遜是一隻可愛的貓貓,牠平常最喜歡吃東西了。

然而,近期的食安問題讓普遜非常不安,吃越多東西恐怕會吃下越多的毒素。因此,普遜決定派出牠的胖吉貓夥伴們去監督食品的製造流程。

食品的製造過程通常很複雜,⽽且往往不是由單一工廠製造的,可能會由⼯廠 A 先對原物料做初步處理後,再把半成品運送到工廠 B、C、D,工廠 B、C、D 再各自進行加工後輸送到各自的目的地(可能是賣場或是另⼀個工廠)。

普遜認為,食安問題最主要的原因應該是運送過程不衛生,才會讓食物出問題。為了達到這個目的,普遜決定派遣胖吉貓夥伴們前往幾個食物加工廠臥底。普遜認為有 N 個工廠(編號為 1 到 N )比較有嫌疑,因此牠決定派胖吉貓到這 N 個工廠中的幾個工廠臥底,並希望每一個運輸過程都是處於「被胖吉貓監督」的狀態。如果某個運輸過程的起點工廠或終點工廠有胖吉貓臥底,那麼我們就說這個運輸過程是被胖吉貓監督的狀態。只要每個運送過程都被胖吉貓監督,就可以確保食物的可吃性了!

然而,雖然去工廠臥底會有薪水,但請胖吉貓去臥底需要花費大量的食物,因此會需要巨大的成本,所以普遜想問,如果已經知道了各個工廠間的運輸流程圖,那麼至少需要幾隻胖吉貓才能監督所有的運輸過程呢?還有胖吉貓們應該在去哪幾間工廠臥底? 

Input:

測試資料第一行有一個整數 T,代表接下來有幾組測試資料。 

每組測試資料第一行有兩個整數 N, M ,中間以空格隔開,分別表示普遜預計調查的工廠的數量與運輸路線的數量。

每組測試資料接下來包含 M 行,每行有兩個整數 a, b ,表示有一條 a 號工廠與 b 號工廠之間的運輸路線。保證不會有兩條一樣的運輸路線,不會有環狀的運輸路線,也不會有起點與終點一樣的運輸路線。

 

Output:

針對每組測試資料請輸出兩行,第一行輸出一個整數 X ,表示最少需要幾隻胖吉貓才能監督所有的運輸過程。

第二行輸出 X 個整數,中間以空格隔開,表示胖吉貓們應該到哪幾個地方臥底,請將 X 個整數由小到大輸出,如果不需要胖吉貓臥底的話則輸出空行。如果有多組解的話,請輸出編號最小的工廠編號最小的,如果還是有多組解,那麼請輸出編號第⼆小的工廠編號最小的,依此類推。也就是輸出字典順序最小的解。 

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
4 4
1 2
3 2
1 3
2 4
8 14
1 8
6 4
1 7
5 3
1 2
3 4
5 6
3 1
8 7
2 7
2 4
3 7
5 2
6 7

Sample Output :

2
1 2
4
1 4 5 7

Hint :

Author :

NPSC 2016 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum