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.
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.