2012年12月16日 星期日

11709 - Trust groups


曲奇士怪獸協會(Association of Cookie Monsters,簡稱 ACM)的人事部門注意到了,公司內許多工作團隊的生產力並不如預期,他們深入訪問受影響團隊的員工,並且找到問題的根源:信任(更確切地說,缺乏信任)。有些員工並不信任團隊中其他人,這將讓他們變得沒有幹勁且不高興。因此人事部門想要解決這個問題,他們決定重新組織所有團隊,使得這些團隊可以變得更安定,換句話說,讓他們互相信任的人組織在一起。人事部門將會詢問每個員工並且知道每個人信任誰。此外,如果員工 A 信任員工 B 且員工 B 信任員工 C,那麼員工 A 也將信任員工 C。另外顯然地,每個員工也相信他自己。人事部門想要創造出盡可能少的工作團隊來減少管理上的麻煩(他們也不想工作太辛苦)。

有了這些資訊後,他們連絡了你並且要你寫出一支程式去找出最少安定團隊的數量。

輸入

輸入包含數筆測試資料。每筆測資一開始有一行以空白分隔的兩個整數 P 和 T ($1{\leq}P{\leq}1000$,$0{\leq}T{\leq}999000$)。接著有 P 行,每行有一個人的名字,名字的格式為:姓氏、一個逗號、一個空白和人名(舉例來說,McBride, John 或者 Smith, Peter 之類)。姓氏和名字都是由大小寫英文字所組成長度不超過 10 的字串(沒有任何標點符號和空白),每個完整的人名將不會有重複的。在人名之後有 T 組輸入,代表人和人之間的信賴關係。每組輸入的 2 行各有一個人名,格式如上所述,代表第一行的人信任第二行這個人,所有出現在這兩行的人名也會在那 P 人之中。

輸入將由「0 0」做為結束,這筆不必被處理。

輸出

對於每筆輸入,輸出僅有一個整數的一行,代表可組成安定團隊的最少數目。

範例輸入

3 2
McBride, John
Smith, Peter
Brown, Anna
Brown, Anna
Smith, Peter
Smith, Peter
Brown, Anna
3 2
McBride, John
Smith, Peter
Brown, Anna
Brown, Anna
Smith, Peter
McBride, John
Smith, Peter
0 0

範例輸出

2
3