Ski Accidents

题意翻译

### 题意 有一个由 $n$ 个点 $m$ 条边组成的有向无环图，每个点出度至多为2。您需要标记一些点（**不超过** $\frac{4}{7}n$ 个）。标记一个点 $u$ 将会**删除所有与** $u$ **连接的边**。 您需要找到一种标记点的方案，使得删边后的图中每一条路径至多有一条边。 ### 输入格式 本题**有多组数据**。第一行一个整数 $T$，表示数据组数。 对于每组数据，第一行二整数 $n$ 和 $m$，表示初始图的点数与边数； 接下来 $m$ 行每行二整数 $x$ 与 $y$，表示一条从 $x$ 到 $y$ 的**有向边**，**可能存在重边**。 ### 输出格式 对于每组数据，第一行一个整数 $k$，表示方案中标记的点数（**不超过** $\frac{4}{7}n$ 即可，**不用得到最小值**）； 接下来一行包括 $k$ 个整数表示被标记的点。 保证所有数据有合法的答案。 ### 数据范围 - $1 \leq n \leq 2 \times 10^5$，并且所有数据中 $n$ 的和不超过 $2 \times 10^5$。 - $1 \leq x,y \leq n$

题目描述

Arthur owns a ski resort on a mountain. There are $ n $ landing spots on the mountain numbered from $ 1 $ to $ n $ from the top to the foot of the mountain. The spots are connected with one-directional ski tracks. All tracks go towards the foot of the mountain, so there are no directed cycles formed by the tracks. There are at most two tracks leaving each spot, but many tracks may enter the same spot. A skier can start skiing from one spot and stop in another spot if there is a sequence of tracks that lead from the starting spot and end in the ending spot. Unfortunately, recently there were many accidents, because the structure of the resort allows a skier to go through dangerous paths, by reaching high speed and endangering himself and the other customers. Here, a path is called dangerous, if it consists of at least two tracks. Arthur wants to secure his customers by closing some of the spots in a way that there are no dangerous paths in the resort. When a spot is closed, all tracks entering and leaving that spot become unusable. Formally, after closing some of the spots, there should not be a path that consists of two or more tracks. Arthur doesn't want to close too many spots. He will be happy to find any way to close at most $ \frac{4}{7}n $ spots so that the remaining part is safe. Help him find any suitable way to do so.

输入输出格式

输入格式

The first line contains a single positive integer $ T $ — the number of test cases. $ T $ test case description follows. The first line of each description contains two integers $ n $ and $ m $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the number of landing spots and tracks respectively. The following $ m $ lines describe the tracks. Each of these lines contains two integers $ x $ and $ y $ ( $ 1 \leq x < y \leq n $ ) — indices of the starting and finishing spots for the respective track. It is guaranteed that at most two tracks start at each spot. There may be tracks in which starting and finishing spots both coincide. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print a single integer $ k $ ( $ 0 \leq k \leq \frac{4}{7}n $ ) — the number of spots to be closed. In the next line, print $ k $ distinct integers — indices of all spots to be closed, in any order. If there are several answers, you may output any of them. Note that you don't have to minimize $ k $ . It can be shown that a suitable answer always exists.

输入输出样例

输入样例 #1

2
4 6
1 2
1 3
2 3
2 4
3 4
3 4
7 6
1 2
1 3
2 4
2 5
3 6
3 7

输出样例 #1

2
3 4 
4
4 5 6 7

说明

In the first sample case, closing any two spots is suitable. In the second sample case, closing only the spot $ 1 $ is also suitable.