AT_abc446_f [ABC446F] Reachable Set 2

You are given a directed graph $ G $ with $ N $ vertices and $ M $ edges. The vertices of $ G $ are numbered as vertex $ 1 $ , vertex $ 2 $ , $ \ldots $ , vertex $ N $ , and the $ i $ -th edge ( $ 1\leq i\leq M $ ) goes from vertex $ U_i $ to vertex $ V_i $ . Solve the following problem for $ k=1,2,\ldots,N $ . > Takahashi's goal is to delete some (possibly zero) vertices from $ G $ , along with all edges having those vertices as an endpoint, so that the following condition is satisfied. > > - The only vertices reachable from vertex $ 1 $ by traversing zero or more edges are vertices $ 1,2,\ldots,k $ . > > Determine whether he can achieve his goal, and if so, find the minimum number of vertices he needs to delete to achieve it.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_M $ $ V_M $

Output $ N $ lines. The $ i $ -th line ( $ 1\leq i\leq N $ ) should contain the answer to the problem for $ k=i $ . Here, for each problem, output $ -1 $ if it is impossible for Takahashi to achieve his goal, and otherwise output the minimum number of vertices that need to be deleted to achieve his goal.

### Sample Explanation 1 - For $ k=1 $ , the goal can be achieved by deleting vertex $ 2 $ . Note that vertices $ 3,4,5 $ are already unreachable from vertex $ 1 $ without deleting them. The goal cannot be achieved without deleting at least one vertex, so output $ 1 $ on the first line. - For $ k=2 $ , the goal can be achieved by deleting vertices $ 4 $ and $ 5 $ . It is impossible to achieve the goal by deleting one or fewer vertices, so output $ 2 $ on the second line. - For $ k=3 $ , Takahashi cannot achieve the goal no matter how he deletes vertices. Thus, output $ -1 $ on the third line. - For $ k=4 $ , the goal can be achieved by deleting vertex $ 5 $ . The goal cannot be achieved without deleting at least one vertex, so output $ 1 $ on the fourth line. - For $ k=5 $ , the goal can be achieved without deleting any vertices. Thus, output $ 0 $ on the fifth line. ### Sample Explanation 2 $ G $ is not necessarily connected. Also, $ G $ may have multi-edges or self-loops. ### Constraints - $ 2\leq N\leq 3\times 10^5 $ - $ 1\leq M\leq 3\times 10^5 $ - $ 1\leq U_i,V_i\leq N $ - All input values are integers.