2011年8月31日 星期三

11504 - Dominos

看著骨牌一個接一個倒下很有趣,但有時候排的不夠好的話,就必須以手動的方式來推倒骨牌。對於一組已經排好的骨牌,請你判斷使每個骨牌皆倒下最少需要用手推倒幾次。

Input Specification

輸入的第一列有一個整數表示測試資料的組數。每組測試資料的第一列有兩個整數 n, m,皆小於100,000,n 表示骨牌數,m 表示接下來有 m 列骨牌排列的資訊,每筆資訊有兩個整數 x, y,表示若編號 x 的骨牌倒下的話,則編號為 y 的骨牌就會被推倒。骨牌編號為1 ~ n。

Sample Input

1
3 2
1 2
2 3

Output Specification

請針對每組測試資料輸出一個整數,表示最少需要用手推倒幾次,才能使所有骨牌倒下。

Output for Sample Input

1

原文出處

沒有留言:

張貼留言