QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB

# 788. 支配树

统计

题目描述

给定一张 $n$ 个点的有向图 $G=(V,E)$,保证 $1$ 号点可达其余所有点。

如果在删除点 $u$ 后,$1$ 与 $v$ 不再联通,则称 $u$ 支配点 $v$。特别地,每个点支配其本身。

你需要对每个点计算出它能支配多少点。

输入格式

输入的第一行包含两个整数 $n,m$。

接下来 $m$ 行,每行两个整数 $u,v$,描述一条从 $u$ 到 $v$ 的有向边。

输出格式

输出一行,包含 $n$ 个整数,其中第 $i$ 个整数描述 $i$ 号点所支配的点的数量。

样例数据

样例 1 输入

3 3
1 2
1 3
2 3

样例 1 输出

3 1 1

样例 2 输入

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

样例 2 输出

5 2 1 1 1

子任务

对于所有数据,$1 \leq n \leq 5 \times 10^5, 1 \leq m \leq 10^6$。