SP7779 ANARC09G - Stock Chase

我得承认，去年我提议的解决银行现金危机的计划并没有真正解决整个经济问题。事实上，公司手头的现金并不多，它们的主要资产是其他公司的股票。公司之间相互持有股份是很常见且被接受的。问题复杂化是因为两家公司可能同时持有对方的股份。仔细想想，这意味着公司有可能（间接地）控制自己的股份。 新的市场监管规定即将实施：任何公司都不得以任何形式控制自己的股份，无论是直接还是间接。证券市场管理局正在寻求一个软件解决方案，以便检测可能导致公司控制自己股份的股份购买行为。您可以想象这种情景：公司 A 购买公司 B 的股份，接着公司 B 购买公司 C 的股份，然后公司 C 再购买公司 A 的股份。前两次交易都是合理的，但第三次则必须被阻止，因为这会导致三个公司都（间接地）控制了自己的股份。程序会按时间顺序接收所有的交易记录，并应拒绝任何可能导致公司控制自己股份的交易，而其它交易则允许通过。

程序会处理一个或多个测试用例。每个测试用例用 $T + 1$ 行描述。第一行包含两个正整数：$0 < N \leq 100,000$ 和 $0 < T \leq 100,000$，它们分别表示公司的数量和交易的数量。接下来的 $T$ 行中，每行包含两个整数 $X_i$ 和 $Y_i$，表示第 $i$ 笔交易中，公司 $X_i$ 购买了公司 $Y_i$ 的股份。

对于每个测试用例，输出一行： ``` k. R ``` 其中 $k$ 是测试用例的序号（从 1 开始），$R$ 是应被拒绝的交易数量。

- $0 < N \leq 100,000$ - $0 < T \leq 100,000$ **本翻译由 AI 自动生成**