Maximum Problems Solved

You are given T test cases. In each test case, there are P problems and D dependencies. Each dependency is represented as a pair (X, Y) which indicates that problem Y can only be attempted after problem X is solved. Your task is to determine the maximum number of problems that can be solved in sequence obeying the dependencies. If there exists a cycle in the dependency graph (making it impossible to solve all problems without violating the order), output \(-1\).

This problem can be solved by performing a topological sort on the directed graph. The ordering is possible only when the graph is a Directed Acyclic Graph (DAG). Otherwise, a cycle is detected and you should return \(-1\).

inputFormat

The first line contains an integer T, the number of test cases.

For each test case:

• The first line contains two integers P and D, representing the number of problems and dependencies.
• The following D lines each contain two integers X and Y, indicating that problem Y can only be attempted after solving problem X.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing the maximum number of problems that can be solved in sequence. If it is not possible to solve all problems due to a dependency cycle, output \(-1\) for that test case. Output is written to standard output (stdout).

## sample

2
5 4
1 2
2 3
3 4
4 5
4 4
1 2
2 3
3 4
4 2

5
-1

</p>