We are given a regular polygon with
vertices. Let's choose
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
and
(
,
), separated with a single space
and representing the number of vertices of the polygon and the number of selected diagonals.
Following
lines contain descriptions of diagonals. Each line contains two integers
and
(
), separated with a single space and representing diagonal, which joins vertex number
with
vertex number
(polygon's vertices are numbered with natural numbers from
to
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:
and
(
,
),
separated with a single space and representing numbers of diagonals that intersect.
In case of multiple correct answers, your program can output any one of them.
Diagonals are numbered in order of occurrence in the input.
For the input data:
6 4 3 6 1 4 6 2 2 5
the correct result is:
2 3
and for the input data:
6 2 1 3 1 5
the correct result is:
NIE

In the image above, solid lines represent diagonals from the first input, while stroked lines represent diagonals from the
second input.
Task author: Jakub Radoszewski.
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.