There is a group of N students numbered from 1 to N. Some of the students know each other.You are given this information by M pairs each of form (ai,bi) denoting that person ai and bi know each other.
The professor wants to conduct a group activity and for this activity he needed either 2 or 3 group of students.The criteria of dividing the students in groups is that only those students who know any of the student in a group can go in that group.Groups are formed such that student of one group does not know student of other group.
Please help the professor to group them.
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 students 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 Professor can conduct this activity and "NO" (without quotes) otherwise
- 1 ≤ T ≤ 103
- 1 ≤ N ≤ 105
- 0 ≤ M ≤ 106
- 1 ≤ ai, bi ≤ N
- The sum of N over all test cases in a single test file does not exceed 105
- The sum of M over all test cases in a single test file does not exceed 106
Input: 2 5 4 1 2 1 3 3 4 4 5 8 9 1 2 2 3 3 1 2 4 3 4 3 5 6 8 7 6 7 8 Output: NO YES
|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, 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