H. Decent Path Around Bajtów
time limit per test
5 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

The road network of Bajtów is a graph consisting of $$$n$$$ intersections connected by $$$m$$$ roads. Each road can be either unidirectional or bidirectional. To simplify the road policies and ease the traffic, the city administrators want to make all roads unidirectional, picking an orientation for every bidirectional road.

As Bajtów is a popular tourist destination, there was a petition to make some roads into a directed cycle so that the "Fantastic Tour Around Bajtów" could be offered as a new tourist attraction. But unfortunately, the road network turned out to have a curious property: no matter how bidirectional roads were directed, the resulting graph would never contain a cycle!

To make up for this, Bajtów authorities decided to pick an orientation such that the longest possible path in the road network would be as long as possible. This way, at least the "Decent Path Around Bajtów" could be arranged. Your goal is to calculate the maximum length of a path over all possible orientations.

Input

The first line of input contains the number of test cases $$$Z$$$ ($$$1 \leq Z \leq 10\,000$$$). The descriptions of the test cases follow.

The first line of a test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 500\,000$$$, $$$1 \leq m \leq 500\,000$$$) – the number of intersections and the number of roads respectively. The next $$$m$$$ lines describe the road network. Each line contains a road description in one of two following formats:

  • u -> v: a unidirectional road from $$$u$$$ to $$$v$$$;
  • u -{}- v: a bidirectional road between $$$u$$$ and $$$v$$$.

In both cases, the values $$$u$$$ and $$$v$$$ are distinct integers satisfying $$$1 \leq u, v \leq n$$$. Each unordered pair of vertices $$$\{u,v\}$$$ appears at most once. The road network is guaranteed to have no orientations that would contain a directed cycle.

The sum of $$$n$$$ over all test cases does not exceed $$$1\,000\,000$$$. The sum of $$$m$$$ over all test cases does not exceed $$$1\,000\,000$$$.

Output

For each test case, print a single line containing the maximum possible number of edges in a path over all possible orientations.

Example
Input
1
6 7
1 -> 2
1 -> 4
2 -> 3
2 -- 5
4 -> 5
5 -> 6
3 -> 6
Output
5