Code Submission Evaluation System Login

HIIT Open 2018

Start:2018-05-26 11:00:00
End:2018-05-26 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2018 - Monotonic

Monotonic

Time limit:2.00 s
Memory limit:512 MB

You are given a program $P$ that manipulates an array of $n$ elements (the elements are arbitrary natural numbers). We will use $x[ i ]$ to denote the current value of array element $i$, for $1 \le i \le n$. The program consists of $m$ "compare" operations: $s(i,j)$ swaps $x[ i ]$ and $x[ j ]$ if $x[ i ] > x[ j ]$.

We say that program $P$ is a sorter if, given any input array (arbitrary elements in an arbitrary order), after running $P$, all elements are in a nondecreasing order, that is, $x[1] \le x[2] \le \dotso \le x[n]$.

Now the program that you are given may not be a sorter. However, repeating the same program for some $k$ number of times might give a sorter!

Your task is to find the smallest $k$ such that the program formed by concatenating $k$ copies of $P$ is a sorter, or report that such a $k$ does not exist.

Input

The first input line has an integer $t$: the number of test cases.

Each test case starts with a line with two integers $n$ and $m$. After that you will have a description of the program: there are $m$ lines, each line with two numbers, $i$ and $j$. Such a line denotes a compare operation $s(i,j)$.

Output

For each test case, print one integer $k$: the smallest number of repetitions of the program that are needed to form a sorter. If such a number does not exist, print $-1$.

Limits
Example

Input:
3
4 4
1 2
3 4
1 2
3 4
4 3
1 2
2 3
3 4
2 1
1 2


Output:
-1
3
1


Explanations: