All submissions for this problem are available.Remy, a chef, is preparing a dish for a group of food reviewers. The dish requires $n$ ingredients, but Remy knows that these reviewers are picky, and a bad review could cost him his career. In specific, for each ingredient, Remy has two brands of that particular ingredient, and he knows that the reviewers dislike $k$ pairs of brands from different ingredients being put together in the same dish. Remy doesn’t know what to do now, so he asks you this: given the $k$ pairs, is it possible to cook a dish that the reviewers wouldn’t dislike? ###Input: - The first line contains $t$, the number of test cases. $t$ test cases follow. - The first line of each test case contains 2 integers $n$ and $k$, the number of ingredients and the number of disliked pairs, respectively. - $k$ lines follow, and each line contains 4 integers $ing_1$, $b_1$, $ing_2$, $b_2$, which indicates that brand $b_1$ of ingredient $ing_1$ does not go well with brand $b_2$ from ingredient $ing_2$. ###Output: For each testcase, if it is possible to cook a dish satisfying the constraints, print “YES” in a new line, else print “NO”. ###Constraints - $1 \leq t \leq 200$ - $1 \leq n, k \leq 10^6$ - Sum of $n$ over all testcases $\leq 10^6$ - Sum of $k$ over all testcases $\leq 10^6$ - $b_i = $ $1$ or $2$ - $1 \leq ing_i \leq n$ ###Sample Input: 2 3 4 1 2 2 2 1 2 2 1 1 1 3 2 1 1 3 1 3 4 1 2 2 2 1 1 2 1 2 2 3 2 1 1 3 1 ###Sample Output: NO YES ###EXPLANATION: You can verify that no combination of brands can satisfy the constraints mentioned in the first testcase. For the second testcase, picking brand 2 of ingredient 1, brand 1 of ingredient 2 and brand 2 of ingredient 3 will satisfy the given constraints.
|Time Limit:||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, 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