10851085 SUSTech Online Judge
Problem 1085 --Proposition equivalence

1085: Proposition equivalence

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 253  Solved: 56
[Submit][Status][Web Board]


In your discrete mathematics class, your teacher gives you a question:

There are n propositions. Now our goal is to prove they have the same equivalence. We say two propositions x and y are equivalence if x implies y and y implies x. Now we have m deductions. An deduction denoted x y means x implies y. Can you find the minimum deduction times we need to achieve our goal? If we cannot achieve our goal, print -1.

Note: Some deduction may be the same. 


The first line will be an integer T. (1 <= T <= 50) T is the number of test cases.

For each test case, the first line will be two integers n and m. n is the number of propositions and m is the number of deductions we have known. (1 <= n <= 20000, 0 <= m <= 50000)

For the following m lines, each line will be two integers x y, meaning we have known x implies y.


For each test case, print the minimum number of deductions we have to make.

Sample Input

4 4
1 2
2 1
2 3
3 2
2 0

Sample Output



For the first sample, we already know 1, 2
and 3 are equivalent. We need to prove 4 is equivalent to any of them. We need
to do 2 deductions. 4<->1 or 4<->2 or 4<->3 are both legal.

For the second sample, we know nothing. So
we need to prove 1<->2 by ourselves. The answer is 2.