Searching for a Biclique

All submissions for this problem are available.
### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK106/hindi/BICLIQUE.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK106/mandarin/BICLIQUE.pdf), [Russian](http://www.codechef.com/download/translated/COOK106/russian/BICLIQUE.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK106/vietnamese/BICLIQUE.pdf) and [Bengali](http://www.codechef.com/download/translated/COOK106/bengali/BICLIQUE.pdf) as well. A *complete bipartite graph* or *biclique* is a special kind of bipartite graph. If we denote the two partitions of vertices of this graph by $A$ and $B$, then such a biclique is denoted by $K_{A, B}$ and satisfies the following conditions:  For each pair of vertices $a, b$ ($a \in A$, $b \in B$), there is an edge between vertices $a$ and $b$.  For each pair of vertices $u, v \in A$, there is no edge between these vertices.  For each pair of vertices $u, v \in B$, there is no edge between these vertices either. You are given a simple graph with $N$ vertices (numbered $1$ through $N$) and $M$ edges. Note that this graph is not necessarily bipartite. You are also given an integer $k$. Determine whether the graph contains the biclique $K_{2, k}$ as a subgraph at least once, i.e. whether it is possible to obtain $K_{2, k}$ by removing some (possibly zero) vertices, all edges adjacent to the removed vertices and some (possibly zero) more edges. ### Input  The first line contains three spaceseparated integers $N$, $M$ and $k$.  Each of the following $M$ lines contains two spaceseparated integers $u$ and $v$ denoting that there is an edge between vertices $u$ and $v$. ### Output Print a single line containing the string `"YES"` if the graph contains $K_{2, k}$ or `"NO"` if it does not (without quotes). ### Constraints  $1 \le N \le 2,000$  $0 \le M \le N(N1)/2$  $1 \le k \le 10$  $1 \le u, v \le N$  the graph does not contain any selfloops or multiple edges ### Example Input ``` 5 10 3 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5 ``` ### Example Output ``` YES ```Author:  erfaniaa 
Editorial  https://discuss.codechef.com/problems/BICLIQUE 
Tags  cookoff, cook106, erfaniaa 
Date Added:  16052019 
Time Limit:  0.5 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, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions