Lionel and Lex
All submissions for this problem are available.
Lex Luthor is a genius, albeit evil. Vertex Cover is an NP-hard problem. Lex Luthor's father, Lionel, is abusive. But even he knows that Lex cannot solve such a hard problem. He gives Lex an easier problem. Given the fact that in the graph G given to Lex, the Vertex-Cover has size strictly less than k or strictly greater than 2k, for a given integer k. Help poor Lex to tell the answer.
The first line contains 3 integers, the number of vertices, n, the number of edges, m and the number, k.
- m lines follow, with 2 integers, u and v denoting an edge between u and v.
For each test case, print "Case 1" is the Vertex Cover is lesser than k and "Case 2" if it is the other case.
- k is non zero
Input: 6 6 1 1 2 2 3 3 4 4 5 5 6 6 1 Output: Case 2
Example case 1.The minimum vertex cover is of size 3, hence Case 2
|Time Limit:||1 - 2 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, CLOJ, FS|
Fetching successful submissions