H. Edge Reversal
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a directed graph with $$$n$$$ vertices and $$$m$$$ edges.

Choose a subset of its edges and reverse every chosen edge. Reversing an edge $$$(u, v)$$$ replaces it with $$$(v, u)$$$.

Find the minimum number of chosen edges such that every vertex has an in-degree of at least $$$1$$$ after the reversals. If no such subset exists, print $$$-1$$$.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 100$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2000$$$, $$$0 \le m \le 10000$$$).

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), representing a one-way path from vertex $$$u$$$ to vertex $$$v$$$.

The input graph contains no two edges with the same ordered pair of endpoints. It may contain both $$$(u, v)$$$ and $$$(v, u)$$$. After the reversals, multiple edges with the same ordered pair of endpoints are allowed.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$10000$$$.

Output

For each test case, print one integer — the minimum number of edges that must be reversed. If no solution exists, print $$$-1$$$.

Example
Input
5
3 3
1 2
1 3
2 3
4 4
1 2
2 3
4 3
1 4
3 2
1 2
2 3
2 2
1 2
2 1
1 0
Output
1
2
-1
0
-1
Note

In the first test case, it is sufficient to replace $$$(1, 3)$$$ with $$$(3, 1)$$$. The three resulting edges form a directed cycle, and every vertex has an in-degree of $$$1$$$.

In the second test case, one can replace $$$(1, 2)$$$ with $$$(2, 1)$$$ and $$$(2, 3)$$$ with $$$(3, 2)$$$. It can be shown that reversing only one edge is insufficient.