Chef and Friends
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef invited N of his friends in his birthday party. All the friends are numbered from 1 to N. Some of the friends might know each other. You are given this information by M pairs each of form (ai, bi), denoting that the persons ai and bi know each other.
Chef wants all of his guests to seat at the two tables set up for dinner. He wants that all the people sitting at a table must know each other, otherwise they will feel awkward with mutual eating habits. Chef is okay if a table is not occupied by any person. Chef is worried whether all the guests can seat at the dinner tables in the desired way.
Please help Chef fast to identify whether his worry is real or not!! The delicacies at the table are getting cold.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M, denoting the number of Chef's friends and the number of pairs representing information whether two person know each other or not.
The next M lines contain two space-separated integers ai and bi, denoting that persons ai and bi know each other.
For each test case, output a single line containing word "YES" (without quotes) if Chef can divide all of his friends into two groups that in each group all the people know each other and "NO" (without quotes) otherwise.
- 1 ≤ T ≤ 103
- 1 ≤ N ≤ 103
- 0 ≤ M ≤ 106
- 1 ≤ ai, bi ≤ N
- The sum of N over all test cases in a single test file does not exceed 104
- The sum of M over all test cases in a single test file does not exceed 106
SubtasksSubtask #1 (30 pts)
- 1 ≤ N ≤ 10
- Original constraints
Input: 3 3 2 1 2 2 3 4 3 1 2 2 3 2 4 6 7 1 2 1 3 2 3 2 4 4 5 4 6 5 6 Output: YES NO YES
Example case 1.
Table 1: Person 1. Table 2: Persons 2 and 3.
Example case 2.
All guests can't have a seat according to the rule.
Example case 3.
Table 1: Persons 1, 2, 3. Table 2: Persons 4, 5, 6.
|Tags||antoniuk1, bipartite, easy, sept16|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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
If you are still having problems, see a sample solution here.