DCEPC11D - DCE Networks

no tags 

Nancy loves talking to people! When she is not busy holding classes for DCE Coders, she really enjoys chatting with her friends on social networking sites. One day, she realised that apart from her huge network of friends, she is also indirectly connected to a lot of people on these sites, such as friends of her friends, their friends and so on.

Formally, 2 people, A and B are said to be connected if:

  1. They are friends OR
  2. There is at least 1 person who is connected to both A and B.

Now, Nancy wants to know what is the minimum number of people she needs to add as friends, so that she is connected to all the students from DCE. Since you all are her favourite students, she asks for your help. Can you help her out?

Input

The first line contains T, the number of test cases.

The first line of each test case contains 2 integers, N and M. N is the total number of students in the college. Each student is identified by a unique index from 1 to N.

This is followed by M lines. Each line consists of 2 distinct integers, S1 and S2 indicating that S1 is a friend of S2 and vice versa. S1 and S2 lie between 1 and N (inclusive).

You can assume that Nancy always has index 1.

Output

For each test case, output a single line containing the minimum number of friends Nancy needs to add.

Constraints

1 <= T <= 10

1 <= N <= 100000

0 <= M <= min(100000, N * (N-1)/2)

Example

Input:
2
3 1
1 2
6 2
1 2
3 5

Output:
1
3


Added by:dce coders
Date:2013-10-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem