Elevator Simulation: Optimal Travel Sequence

You are given a building with N floors and M elevator requests. Each request is represented by a pair of integers (start, end) which indicates that the elevator must travel from the starting floor to the ending floor. Instead of following the requests sequentially, your task is to determine an optimal order to visit all the distinct floors mentioned in the requests.

The objective is to minimize the total travel distance. Formally, if the sequence of visited floors is \(a_1, a_2, \ldots, a_k\), then the total distance is given by \[ D = \sum_{i=2}^{k} |a_i - a_{i-1}|, \] where \(|x|\) denotes the absolute value. In case there are multiple orders with the same minimal distance, choose the lexicographically smallest sequence (comparing element by element).

Note: The number of floors that need to be considered is only those that appear in at least one request. You can assume that the total number of such floors is small enough to allow a brute force solution using permutations.

inputFormat

The first line of input contains two integers N and M separated by a space, where N is the total number of floors in the building and M is the number of elevator requests.

This is followed by M lines, each containing two space-separated integers representing the starting and ending floors for a request.

outputFormat

Output a single line containing the optimal sequence of distinct floors (separated by a space) that minimizes the total travel distance. If there are multiple optimal sequences, output the lexicographically smallest one.

5 3
1 3
4 5
2 1

1 2 3 4 5