2013年7月11日 星期四

1160 - X-Plosives


X-Plosives

秘密組織研發了一種當有特殊條件下才會進行爆炸的炸藥。對於兩個不同的簡單化合物混合,稱之為 binding pair。當 N > 2,混合 N 個不同的 binding pairs,且其中有 N 種簡單化合物將會引起強大爆炸。例如:binding pairs  A+B, B+C, A+C (三對,三種化合物) 將會引起爆炸,但是 A+B, B+C, A+D (三對, 四種化合物) 則不會爆炸。


你不是秘密組織的特工,但是只有一個人在負責傳遞部分有一個危險的問題:

依序接收到的 binding pairs 將被放置在貨船上,然而你必須避免放置在同一處產生爆炸,所以在放置一些 pairs 後,你會收到一組 pair,如果放進去會產生爆炸則拒絕它,反之接收它並放入貨船中。

例如,你依序收到 A+B, G+B, D+F, A+E, E+G, F+H,會先將前 4 個放入貨船,然後將會拒絕 E+G,因為存在 A+B, G+B, A+E, E+G 會產生爆炸的疑慮,最後將會接收 F+H。

計算有多少被拒絕的 binding pairs

Input

輸入會有多組測資,每組間會有空白隔開。將會用整數取代字母表示一個化合物,輸入有數行, 每行上會有兩個整數 (範圍 0 到 105),最後一行以一個整數 –1,表示一組測資結束。

假設不會有重覆的 binding pairs。.

Output

對於每組測資,輸出被拒絕的個數。

Sample Input
1 2
3 4
3 5
3 1
2 3
4 1
2 6
6 5
-1

Sample Output
3