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.
There is no restriction on the final degree of the nodes and
there is no self loop or multiple edges in the final graph
- 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.
- For each test case, output a single line containing the required answer.
- 1 ≤ T ≤ 100000
- 1 ≤ N ≤ 100000
- 1 ≤ E ≤ 100000
- 1 ≤ a,b ≤ N
- Sum of E over all testcases <= 1000000
Input: 1 3 1 1 2 Output: 1
Only one more edge can be added either (1,3) or (2,3)
|Tags||bipartite, graph, ipc151a, ipcquestion, skullcrackers|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.