Acyclic Graph

All submissions for this problem are available.
Given a acyclic graph with N nodes and E undirected edges and degree (number of edges incident on that node) of every node is less than 3.
Find the maximum number of edges that can be added, such that there is no cycle of odd length in the final graph.
Note:
There is no restriction on the final degree of the nodes and
there is no self loop or multiple edges in the final graph
Input
 The first line of the input contains an integer T denoting the number of test cases.
 The first line of each test case contains a 2 integers N and E denoting the number of nodes and number of edges.
 Next E lines contains 2 integers a and b denoting that there is an edge between node a and b.
Output
 For each test case, output a single line containing the required answer.
Constraints
 1 ≤ T ≤ 100000
 1 ≤ N ≤ 100000
 1 ≤ E ≤ 100000
 1 ≤ a,b ≤ N
 Sum of E over all testcases <= 1000000
Example
Input: 1 3 1 1 2 Output: 1
Explanation
Only one more edge can be added either (1,3) or (2,3)
Author:  skullcrackers 
Editorial  http://discuss.codechef.com/problems/AGRAPH 
Tags  bipartite, graph, ipc151a, ipcquestion, skullcrackers 
Date Added:  7102015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 