前往首都

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

给定一张有 $n$ 个顶点、$m$ 条边的有向图，所有边长度均为 $1$，并保证从顶点 $1$ 可以到达每个顶点。令 $d_i$ 表示从顶点 $1$ 到顶点 $i$ 的最短距离。

从一个顶点开始沿有向边行走。对于边 $u\to v$：若 $d_u<d_v$，可以经过任意多次；若 $d_u\ge d_v$，整条行走路径中至多经过一次这类边。

对每个起点 $i$，求所有可以到达的顶点 $v$ 中 $d_v$ 的最小值。

输入格式

第一行包含测试用例数 $t$。

每个测试用例的第一行包含两个整数 $n,m$。接下来 $m$ 行，每行包含两个整数 $u,v$，表示一条有向边 $u\to v$。

输出格式

对每个测试用例输出一行 $n$ 个整数，第 $i$ 个整数为从顶点 $i$ 出发能到达的顶点中最小的 $d$ 值。

样例输入 1

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

样例输出 1

0 0 1 2 0 1
0 0
0 0 2 1 1 0

数据范围

对于所有数据，$1\le t\le10^4$，$2\le n,m\le2\times10^5$，$1\le u,v\le n$；所有测试用例的 $n$ 之和、$m$ 之和均不超过 $2\times10^5$。