【模板】支配树

题目背景

模板题,无背景

题目描述

给定一张有向图,求从1号点出发,每个点能支配的点的个数(包括自己)

输入输出格式

输入格式


第一行两个正整数$n,m$,表示点数和边数 接下来$m$行,每行输入两个整数$u,v$,表示有一条$u$到$v$的有向边

输出格式


一行输出$n$个整数,表示每个点能支配的点的个数

输入输出样例

输入样例 #1

10 15
1 2
2 3
3 4
3 5
3 6
4 7
7 8
7 9
7 10
5 6
6 8
7 8
4 1
3 6
5 3

输出样例 #1

10 9 8 4 1 1 3 1 1 1 

说明

$n\le2*10^5,m\le3*10^5$