Stock Chase#1277
New market regulation is being implemented: No company can control shares in itself, whether directly or indirectly. The Stock Market Authority is looking for a computerized solution that will help it detect any buying activity that will result in a company controlling its own shares. It is obvious why they need a program to do so, just imagine the situation where company buys shares in , buys in , and then buys in . The first two purchases are acceptable.
The third purchase should be rejected since it will cause the three companies to control shares in themselves. The program will be given all purchasing transactions in chronological order. The program should reject any transaction that could lead to one company controlling its own shares.
All other transactions are accepted.
Your program will be tested on one or more test cases. Each test case is specified on + lines. The first line specifies two positive numbers: (0 < N \leq 234) is the number of companies and (0 < T \leq 100\,000) is the number of transactions. lines follow, each describing a buying transaction. Each transaction is specified using two numbers and where (0 < A,\ B \leq N) indicating that company wants to buy shares in company .
The last line of the input file has two zeros.
For each test case, print the following line:
.
Where is the test case number (starting at one), is the number of transactions that should be rejected.
Note: There is a blank space before .
Example 1