Prateek and Graphs
All submissions for this problem are available.
Prateek loves problems related to Maths and especially he loves solving problems involving even numbers. He has got a task from his teacher to solve a problem on Graph theory.
Given a simple undirected graph containing N vertices and M edges. A step is defined as follows : choose a node with even degree and remove that node and all its incident edges. Now, Continue such steps until there are no even degree nodes available or no node is left. So your task is to minimize the number of steps and decide whether the minimum number of steps is even or odd.
Since Prateek is one of the co-ordinator of Advaita, and he is busy with planning the entire event so he needs your help. Can you solve this problem for him?
The first line contains an integer T, denoting number of test cases. The first line of each testcase contains two integers N and M. Each of the next M lines contains two integers U and V denoting a single edge in G between the vertices labeled U and V.
For each test case, print whether the minimum number of steps is Odd or Even.
- 1 ≤ T ≤ 10
- 1 ≤ N, M ≤ 100000
- Sum of M over all test cases is less than 200000
Input: 2 4 3 1 2 2 3 3 4 5 5 1 2 2 3 3 4 4 5 5 1 Output: Even Odd
|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, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions