Bajtów 的道路网络是一个由 $n$ 个交叉路口和 $m$ 条道路组成的图。每条道路可以是单向的，也可以是双向的。为了简化道路管理并缓解交通压力，城市管理者希望将所有道路都变为单向，即为每条双向道路选择一个方向。

由于 Bajtów 是一个热门的旅游目的地，曾有人请愿将一些道路改造成一个有向环，以便提供“Bajtów 奇妙环游”作为新的旅游景点。但不幸的是，该道路网络具有一个奇特的性质：无论双向道路如何定向，生成的图中永远不会包含环！

为了弥补这一点，Bajtów 当局决定选择一种定向方式，使得道路网络中最长路径的长度尽可能大。这样，至少可以安排出一条“Bajtów 体面路径”。你的目标是计算在所有可能的定向方式下，路径长度的最大值。

输入格式

第一行包含测试用例的数量 $Z$ ($1 \le Z \le 10\,000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 500\,000, 1 \le m \le 500\,000$)，分别表示交叉路口的数量和道路的数量。接下来的 $m$ 行描述了道路网络。每行包含以下两种格式之一的道路描述：

• $u \to v$：从 $u$ 到 $v$ 的单向道路；
• $u -- v$：连接 $u$ 和 $v$ 的双向道路。

在这两种情况下，$u$ 和 $v$ 均为满足 $1 \le u, v \le n$ 的不同整数。每对无序顶点 $\{u, v\}$ 最多出现一次。保证该道路网络不存在任何会导致产生有向环的定向方式。

所有测试用例的 $n$ 之和不超过 $1\,000\,000$。所有测试用例的 $m$ 之和不超过 $1\,000\,000$。

输出格式

对于每个测试用例，输出一行，包含在所有可能的定向方式下，路径中包含的边数的最大值。

样例

输入 1

1
6 7
1 -> 2
1 -> 4
2 -> 3
2 -- 5
4 -> 5
5 -> 6
3 -> 6

输出 1

5