Minimum Semesters to Complete Courses

You are given n courses labeled from 1 to n and a list of prerequisites. Each prerequisite is given as a pair \((u, v)\) which means that course \(u\) must be completed before course \(v\). In one semester, you can take any number of courses as long as their prerequisites are met.

Your task is to determine the minimum number of semesters required to complete all courses. Formally, if you can complete the courses in \(k\) semesters, then there exists a partition of courses into \(k\) disjoint sets \(S_1, S_2, \dots, S_k\) such that for every prerequisite \((u, v)\) there exists an index \(i\) where \(u \in S_i\) and \(v \in S_j\) with \(i < j\).

If it is impossible to complete all courses (i.e. there is a cycle), output \(-1\).

The key idea is to perform a level order topological sort (Kahn's algorithm) and count the number of levels (semesters).

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(T\) denoting the number of test cases. For each test case:

• The first line contains two integers \(n\) and \(m\), where \(n\) is the number of courses and \(m\) is the number of prerequisites.
• The next \(m\) lines each contain two integers \(u\) and \(v\), indicating that course \(u\) must be taken before course \(v\).

It is guaranteed that \(1 \leq n \leq 10^5\) and \(0 \leq m \leq 10^5\) in each test case.

outputFormat

For each test case, output a single line to standard output (stdout) containing one integer: the minimum number of semesters needed to complete all courses. If it is impossible, output \(-1\).

## sample

5
5 4
1 2
2 3
3 4
4 5
3 2
1 2
2 3
3 0
4 4
1 2
1 3
2 4
3 4
6 6
1 2
1 3
2 4
3 5
5 6
4 6

5
3
1
3
4

</p>