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.
2
4 4
1 2
2 1
2 3
3 2
2 0
2
2
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.