obilazak
Maja i Jaca in the free time for reading the magazines "Cosmopolitan","Vogue", "Joy", "Viva", "Bravo" and " Health and Beauty", are playing a very interesting game. Jaca on a sheet of paper,so that Maya can not see, draws a convex polygon with N sides and marks the vertices with numbers 1,2,...,N in an arbitrary order,then he draws M diagonals, so that they do not intersect.(except perhaps in the vertices). After that Jaca tells Maja all the pairs of vertices who are either ends of any diagonal or are vertices of any side. Maja needs to guess the order of the vertices that are on the sides of the polygon.
InputIn the first line are the numbers N and M (3 <= N <= 10000, 0 <= M <= N–3). In the next N+M lines are two numbers, which represent a pair of vertices that are connected with a side or a diagonal. The order of the sides and the diagonals is arbitrary.
OutputThe output should contain N lines where every line contains one number. This number should represent the order of the vertices, going through the sides of the polygon. The solution isn't unique- there always exist 2N solutions depending on the chosen starting vertex and the direction of listing the vertices.
Input
Output
5 2
2 4
5 1
1 2
3 5
1 3
2 3
4 1Output
2
3
5
1
4Image: obilazak
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.