All submissions for this problem are available.
Chef has a Pizza outlet and all of the people of Byteland are aware of the special offer by Chef on Wednesday (i.e buy 1 get 1 free). But people of Byteland are health conscious, they don't want to eat two pizzas and hence they always go in such groups (so that they have to pay half price for a pizza).
If a group is not formed they will go on next wednesday. Two people will go together if and only if they are friends (Yes, friendship is transitive). As you know, byteland consists of many special people, one of them is our own Punk-it, who loves Pecorino cheese burst Pizza a lot. He is ready to go with anyone if group can be formed.
The first line of the input contains a single integer T, denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two space-separated integers N (the number of people excluding Punk-it) and M( the number of relations). Each of the following M lines contains two space-separated integers A and B denoting A and B are friends.
For each test case, output a single line containing on interger, denoting the maximum number of people who will enjoy pizza.
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 100000
- 0 ≤ M ≤ 100000
- 1 ≤ A,B ≤ N
- A != B
Input: 2 6 4 1 2 2 3 3 4 5 6 7 4 1 2 2 3 3 4 6 7 Output: 6 8
|Time Limit:||0.1 - 0.13 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions