CAM5 - prayatna PR


help the Prayatna pr team

Well, the annual technical symposium of Department of Computer Technology is around the corner. All that we need, to make it a grand success is Publicity among the peer groups ( ofCourse the sponsors too :P ). We decided to share the job between the student groups. As per the plan we decided to meet people in person and influence them to attend Prayatna. But to meet them we have to go to various student groups. To do so, we had to cut our classes. But being studious. students refused to cut more classes. Instead of meeting every one in person we decided to meet few people such that the person to whom we pass the news will spread it to all his friends. And those friends will pass it to other friends and so on. Your task is to find the number of people to be met by the organizers to spread the news.

Caution: Large I/O

Input

First line of input is 't' - Test cases. Follwed by N, the number of peers in the testcase ( 0 to N-1 ). followed by the number of friend description 'e'. Following are 'e' descriptions of type "a b" denoting 'a' friends with 'b'. If 'a' is friends with 'b' then 'b' is friends with 'a'.

Output

Output contains t line, the number of people, the organizers have to meet in person for each test case.

Example

Input:
2

4
2
0 1
1 2

3
0

Output:
2
3

Explanation

case 1 : 0 is friends with 1; 1 is friends with 2; so if we pass the news to 0 & 3, news will pass it to the entire N peers.

case 2 : no one is friends with any one. So we have to meet every one in person.

Constraints

t = 10
2 <= N <= 100000
0 <= e <= N/2


hide comments
pandey101299: 2019-11-24 13:23:38

thanks @dependra _18 your suggestion is very helpful for me

deependra_18: 2019-11-24 07:57:56

using DSU -use optimisation of path compression and add add smaller group to a larger one

shikhar_may7: 2019-11-06 22:43:34

why is it that DSU gives TLE and DFS gets accepted ?

pallav17: 2019-10-24 17:04:11

can somebody provide a solution for this question in python it is giving runtime error even on setting up recursionlimit ?

Last edit: 2019-10-26 09:38:38
an09mous: 2019-06-27 19:31:58

Can easily be solved using DSU

kushagra_2: 2019-06-22 19:02:11

use faster I/O cost me one WA :(

shanu_im: 2019-06-22 13:10:36

Do not submit in python
you will get a runtime error for no reason

scolar_fuad: 2019-05-28 07:34:10

Ac in One go simple dfs problem for beginner try to bfs to get better time efficiency

dkkv0000: 2019-05-15 08:05:20

dfs rocks!!!!!!!

aquib_ansari: 2019-04-30 07:54:31

Hmm.. DFS didn't work! Connected components did it tho!.


Added by:karthikeyan
Date:2012-01-11
Time limit:0.376s-0.662s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem