3496：山地赛车

一群ACM大佬参加了一场山地赛车比赛。举办方事先给选手发放了比赛地图，地图由多个节点和多条道路组成。为了比赛安全，所有道路都是单向行驶的。比赛要求选手们任意选择起点和终点，以确定一条最长的路径（即经过的道路数量最多），路径最长的选手获胜。这难不倒ACM大佬，于是每个人都规划好了一条最长路径（有可能并列最长的情况，那么保证每条路径都会至少有人选择）。

然而比赛方要考虑一些突发自然状况，例如滑坡、雪崩。由于比赛选手要到达该条道路所处节点时，才能意识到该道路不可行，当一条道路因为自然状况被阻塞时，原先以此道路规划为最长路径的选手骑行到该道路节点时，需要重新规划接下来的路径，以保证总路径尽可能的长，这样一来他们的骑行路径长度有可能会变短；但其它不选择此道路的选手不会受到影响。

举办方希望最终获胜选手的路径长度尽可能长，但道路阻塞可能会导致获胜选手的路径长度很短。

假设只会有一条道路被阻塞，问在最糟糕的情况下，获胜选手的路径长度是多少（即最长路径的最小值）？

多组案例。一个正整数T，表示案例的数量。

每组案例中，第一行由两个整数n和m组成，表示节点的数量和道路的数量。（2<=n<=1e+5，1<=m<=min(n(n-1)/2, 1e+6)

接下来的m行中，每行由两个整数u和v组成，表示一条单向的道路，由节点u到节点v。（1<=u,v<=n且u!=v）

保证任意两个节点之间最多只有一条道路，保证路径图中没有环。

针对每组案例，输出一个整数，表示当其中一条道路被阻塞时，获胜选手路径长度（即所有选手中的最长路径）的最小值。

每组案例输出完都要换行。

4

4 4

1 2

1 3

3 4

2 4

7 6

1 2

2 3

2 5

6 3

7 2

3 4

7 5

1 2

2 3

3 4

5 6

6 7

6 5

1 2

1 4

2 3

4 5

5 6

2

2

0

1

除旧迎新限时题-虎