Codeforces 1368E - Ski Accidents

原文

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 $\frac47n$ spots so that the remaining part is safe. Help him find any suitable way to do so.

Input

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\le n\le 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\le x< y\le 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$ .

Output

For each test case, print a single integer $k$ ( $0\le k\le \frac47n$ ) — 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.

Example

input

output

Note

In the first sample case, closing any two spots is suitable.

In the second sample case, closing only the spot $1$ is also suitable.

大致意思

给出一个有向无环图，所有定点的出度不超过2，入度不做限制，同时限定边的起始点一定比终止点要小（是从山顶到山脚的滑雪道）。

要求去掉其中的一些顶点（不多于 $\frac47n$ ），使得图中没有长度超过2的路径。

思路

贪心想法为从节点1（山顶）向后分层级来遍历，如果是第一条连边则保留，第二条则删除相关联节点。

如之后代码中所表示的level，这里通过level将所有顶点分成三类，下标为节点对应的level，形式化表述如下：

$V_0$ 包含只拥有来自 $V_2$ 入边的顶点
$V_1$ 包含至少有一条来自 $V_0$ 入边，但是没有来自 $V_1$ 入边的顶点
$V_2$ 包含至少有一条来自 $V_1$ 入边的顶点

对应的就是删除所有 $V_2$ 中的顶点，下面来证明为什么可以保证不超过 $\frac47n$ ：

由于 $V_2$ 至少有一条来自 $V_1$ 的边，而一个顶点最多两条出边，所以最多有 $2|V_1|$ 条出边，那么有着 $|V_2|\le 2|V_1|$ ，同理有着 $|V_1|\le 2|V_0|$ 。于是 $n = |V_0|+|V_1|+|V_2|\ge \frac74|V_2|$ ，所以 $|V_2|\le \frac47n$ 。

只需要从山顶到山脚扫描一遍就可以确定哪些是 $|V_2|$ 当中的顶点，这里的时间复杂度为 $O(n)$ 。

注意：如果对整个level数组进行memset操作，有一个 $t=2\cdot 10^5$ 的case会超时！

代码

#include <bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define maxn 200010

int level[maxn];
vector<int> adj[maxn];

int main(){
    IOS;
    int t;
    cin>>t;
    while(t--){
        int n, m;
        cin>>n>>m;
        for(int i=0;i<m;++i){
            int x, y;
            cin>>x>>y;
            adj[y].push_back(x);
        }
        vector<int> ans;
        for(int u=1;u<=n;++u){
            for(int v: adj[u]){
                level[u] = max(level[u], (level[v]+1)%3);
            }
            if(level[u] == 2){
                ans.push_back(u);
            }
        }

        cout<<ans.size()<<endl;
        for(auto i: ans){
            cout<<i<<' ';
        }
        cout<<endl;
        
        memset(level, 0, sizeof(int)*(n+1));
        for(int i=1;i<=n;++i)
            adj[i].clear();
    }
}