Parallel Courses

You are given an integer N which denotes the number of courses numbered from 1 to N and a matrix ‘prerequisites’, in which each row contains exactly two integers ‘A’ and ‘B’ which represents the course ‘A’ has to be studied in some semester before studying course ‘B’.

You are supposed to find the minimum number of semesters required to study all the courses.

If it is impossible to study all the courses, then return -1.

Note :

There is no limitation on taking the number of courses in a particular semester as long as all the prerequisites for taking the course are satisfied.

Input Format :

The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line of each test case contains two integers ‘N’ and ‘M,’ which denotes the number of courses and the number of rows of the matrix ‘prerequisites.’

The next M lines contain two integers, prerequisites[i][0] and prerequisites[i][1], denoting that prerequisites[i][0] has to be studied before prerequisites[i][1].

Output Format :

For each test case, print the minimum number of semesters required to study all the courses.

Print the output of each test case in a separate line.

Constraints :

1<= T <= 50
1 <= N <= 20000
0 <= M <= 20000
1 <= prerequisites[i][0], prerequisites[i][1] <= N
prerequisites[i][0] != prerequisites[i][1], for any valid i

Time Limit: 1 sec