|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||0||0||0||0.000%|
We are given a regular polygon with n vertices. Let's choose m of its diagonals. We would like to know if there is such a pair of diagonals that intersect (having a common end-point does not count as intersection).
Write a program which:
In the first line of the input there are two integers n and m (4 ≤ n ≤ 1 000 000, 2 ≤ m ≤ 10 000 000), separated with a single space and representing the number of vertices of the polygon and the number of selected diagonals. Following m lines contain descriptions of diagonals. Each line contains two integers ai and bi (1 ≤ ai, bi ≤ n), separated with a single space and representing diagonal, which joins vertex number ai with vertex number bi (polygon's vertices are numbered with natural numbers from 1 to n in a counter-clockwise manner). You can assume that each pair of numbers defining a single diagonal defines a valid diagonal (not a single vertex or polygon's edge). All diagonals in the input will be different.
The first and only line of the output should contain:
NIE(i.e. no in Polish), if there is no pair of diagonals that intersect, or
6 4 3 6 1 4 6 2 2 5
6 2 1 3 1 5
In the image above, solid lines represent diagonals from the first input, while stroked lines represent diagonals from the second input.