Unknown Polygon

Each vertex of a regular N-gon is labeled with one distinct integer from 1 to N. Inside the polygon, M diagonals are drawn so that no two diagonals cross. Two segments that share an endpoint are not considered crossing.

For the N sides of the polygon and the M diagonals, only the unordered pair of endpoint labels for each segment was recorded. Given this list of segments, reconstruct the labels around the boundary of the original polygon.

The first line contains two integers N and M. N satisfies 3 <= N <= 10,000, and M satisfies 0 <= M <= N-3.

Each of the next N+M lines contains two integers written on the endpoints of one segment.

Print N integers on the first line, separated by spaces, in the order they appear around the polygon boundary.

The first integer must be 1. Of the two possible directions, print the one whose second integer is smaller.