CSES - HIIT Open 2018 - Monotonic
  • Time limit: 2.00 s
  • Memory limit: 512 MB

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

We say that program PP is a sorter if, given any input array (arbitrary elements in an arbitrary order), after running PP, all elements are in a nondecreasing order, that is, x[1]x[2]x[n]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 kk number of times might give a sorter!

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

Input

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

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

Output

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

Limits

  • 1t101 \le t \le 10
  • 1n151 \le n \le 15
  • 1m15001 \le m \le 1500
  • 1i<jn1 \le i < j \le n

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:

  • First test case: If you give the input (3,4,1,2), the program does not ever change it, no matter how many times you repeat it.
  • Second test case: If you start with input (4,3,2,1), one iteration of the program changes it to (3,2,1,4), which is not yet good. Another iteration changes it to (2,1,3,4), which is not yet good. However, after three iterations any input will be correctly sorted.
  • Third test case: The input is already a sorter, one iteration is enough.