Longest Simple Path in a Directed Road Network

You are given a directed graph representing a road network with N intersections and M one-way roads. Your task is to determine the length of the longest simple path in the network. A simple path is defined as a path which does not visit any intersection more than once.

Formally, given a directed graph \(G=(V,E)\) with \(|V|=N\) and \(|E|=M\), find the maximum length \(L\) such that there exists a sequence of distinct intersections \(v_1, v_2, \dots, v_{L+1}\) satisfying \((v_i, v_{i+1}) \in E\) for all \(1 \le i \le L\).

Note: The input size is small enough so that a depth-first search (DFS) solution with recursion and backtracking is practical.

inputFormat

The first line of input contains an integer T, the number of test cases. Each test case is described as follows:

• The first line contains two integers N and M: the number of intersections and the number of roads.
• The next M lines each contain two integers u and v, representing a directed road from intersection u to intersection v.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single integer on a separate line: the length of the longest path (i.e. the maximum number of roads on a valid simple path) that can be obtained in the given road network.

Output is written to standard output (stdout).

## sample

1
3 2
1 2
2 3

2

</p>