Description

Given a directed graph, find the length of the smallest cycle in the graph.

A cycle in a graph is a path that starts and ends at the same vertex, passing through other vertices without repeating any edge. The length of a cycle is the number of the edges that form the cycle.

Your task is to determine the length of the smallest cycle present in the graph. If there are multiple cycles, you should identify the one with the least length. If the graph has no cycles, you should indicate that by returning -1 for that test case.

Input

The first line contains a number T (1 ≤ T ≤ 5), indicating the number of testcases.

For each test case:

• The first line contains two positive integers n and m, where 1 ≤ n ≤ 500 and 1 ≤ m ≤ 250000. These represent the number of vertices and edges in the graph.
• The vertices are numbered from 1 to n.
• The next m lines each contain two integers i, j (1 ≤ i, j ≤ n), describing a directed edge from vertex i to vertex j. 

Output

For each test case, output the length of the smallest cycle in the graph. If the graph has no cycles, output -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss