Stock Chase

I have to admit, the solution I proposed last year for solving the bank cash crisis did not solve the whole economic crisis. As it turns out, companies do not have that much cash in the first place. What they own is mostly shares in other companies.

It is common, and acceptable, for one company to own shares in another. What complicates the issue is for two companies to own shares in each other at the same time. If you think about it for a moment, this means that each company now (indirectly) controls its own shares.

A new market regulation is being put in place: no company may control shares in itself, whether directly or indirectly. For example, imagine company $A$ buying shares in $B$, $B$ buying shares in $C$, and then $C$ buying shares in $A$. The first two purchases are acceptable, but the third must be rejected, since it would make all three companies control their own shares.

The program is given every buying transaction in chronological order. It must reject any transaction that could lead to a company controlling its own shares, and accept all other transactions. Report how many transactions are rejected.

The input consists of one or more test cases. Each test case is given on $T + 1$ lines. The first line contains two positive integers $N$ and $T$, where $N$ is the number of companies ($0 < N \le 234$) and $T$ is the number of transactions ($0 < T \le 100000$). Each of the following $T$ lines describes one buying transaction as two integers $A$ and $B$ ($0 < A, B \le N$), meaning that company $A$ wants to buy shares in company $B$.

The last line of the input contains two zeros.

For each test case, print the following single line:

k. R

where $k$ is the test case number (starting at one) and $R$ is the number of transactions that must be rejected.