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 straight-line 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+1-th segment but surprisingly it turned out that it was impossible to connect any pair of points by straight-line 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 straight-line 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 non-intersecting segments that are given, you will never be able to place M+1th segment.
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 straight-line segments
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
- 1 ≤ T ≤ 6000
- 1 ≤ N ≤ 7*104
- 1 ≤ M ≤ 3*105
- sum of all N in one test file doesn't exceed 7*105
- no segment connects a point with itself
- each pair of points is connected no more than by one segment
- Subtask 1 : 1 ≤ N ≤ 5 : ( 20 pts )
- Subtask 2 : no additional constraints: ( 80 pts )
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
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 straight-line segment(and even not straight-line) 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.
|Tags||graph, hard, june15, pavel1996|
|Time Limit:||5 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.