Connect Points

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
One day Leha got bored during his geometry class. But his teacher was very careful so the boy had to pretend that he was solving some geometry problem. At first glance he started drawing some senseless stuff. He marked N pairwise different points on the plane and then connected M pairs of these points by straightline segments. No 3 points lie on the same line. None of these segments intersect(maybe except at the initial N points). Then Leha tried to draw the M+1th segment but surprisingly it turned out that it was impossible to connect any pair of points by straightline segment which wouldn't intersect with any of the previous segments.
Let's enumerate points from 1 to N. You are given M pairs of integers  numbers of points which are connected by the each straightline segment. The question is: whether it's possible to choose N points on the Euclidean plane in any way such that they will always fit the situation described above. That is, try to place the given N points and M nonintersecting segments that are given, you will never be able to place M+1th segment.
Input
The first line contains one integer T  the number of test cases. Each test case starts with a line containing two integers N and M. M lines containing a pair of integers each follow describing pairs of points connected by straightline segments
Output
For each test case output a single line containing1 if it's possible to find points which will satisfy the problem statement and 0 otherwise
Constraints
 1 ≤ T ≤ 6000
 1 ≤ N ≤ 7*10^{4}
 1 ≤ M ≤ 3*10^{5}
 sum of all N in one test file doesn't exceed 7*10^{5}
 no segment connects a point with itself
 each pair of points is connected no more than by one segment
Subtasks
 Subtask 1 : 1 ≤ N ≤ 5 : ( 20 pts )
 Subtask 2 : no additional constraints: ( 80 pts )
Example
Input: 3 3 3 1 2 2 3 1 3 3 2 1 3 2 3 4 6 1 2 1 3 1 4 2 3 2 4 3 4 Output: 1 0 1
Explanation
In the first test case we can draw triangle on the plane. Obviously no pair of segments will intersect and we can't add any more straightline segment(and even not straightline) so the answer is 1
In the second test case we can draw 3 points and connect 1 and 3 and 2 and 3. But we can add one more(1 and 3) so the answer is 0
In the last test case we can draw a triangle and a point inside it connected to 3 vertexes of the triangle. As in the first test case we can't connect some new pair so the answer is 1 too.
Author:  pavel1996 
Editorial  http://discuss.codechef.com/problems/CONPOIN 
Tags  graph, hard, june15, pavel1996 
Date Added:  9052015 
Time Limit:  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, 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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions