Minimizing Lexicographical Order of Isolated Edges

Given an undirected graph with \(n\) vertices and \(m\) edges (with no self‐loops or multiple edges, although the graph may be disconnected), each edge is assigned a distinct label from \(1\) to \(m\) according to the input order. An edge is called an isolated edge if and only if both of its endpoints have been removed.

You are required to choose an order in which to remove all vertices. When a vertex is removed, any edge that has both endpoints already removed becomes isolated at that moment. If more than one edge becomes isolated at the same time, they are considered to become isolated in the increasing order of their labels. Let \(P_i\) denote the label of the edge that becomes isolated as the \(i\)th isolated edge event. Your goal is to produce a vertex removal order that minimizes the sequence \(\langle P_1, P_2, \ldots,P_m \rangle\) in lexicographical order.

Observation: When an edge \(e=(u,v)\) becomes isolated, its event time is \(\max\{pos(u), pos(v)\}\) where \(pos(x)\) is the position in the removal order. In order to make the isolated edge events lexicographically as small as possible, for an edge with a small label we want both its endpoints removed as early as possible. Conversely, if a later decision delays the removal of an endpoint of a low‐labeled edge, that edge might appear later than necessary in the isolated edge sequence, worsening the lexicographical order.

A greedy strategy works as follows. Process the edges in increasing order of their labels (i.e. in input order). For each edge connecting vertices \(u\) and \(v\):

• If neither \(u\) nor \(v\) has been scheduled for removal, schedule both immediately (with the smaller vertex placed first to help future decisions).
• If exactly one endpoint has been scheduled, then schedule the other endpoint as soon as possible.
• If both endpoints are already scheduled, do nothing.

After processing all edges, append any remaining unscheduled vertices (in increasing order, for instance) to complete the removal order. This guarantees that for each edge with a small label, both its endpoints are removed as early as possible, thereby minimizing the lexicographical order of the isolated edges sequence.

Input Format: The first line contains two integers \(n\) and \(m\). Each of the next \(m\) lines contains two integers \(u\) and \(v\) indicating an edge between vertices \(u\) and \(v\). The edges are given in the order of their labels from \(1\) to \(m\). It is guaranteed that \(1 \le u,v \le n\) and \(u \neq v\).

Output Format: Output a permutation of the vertices, which is the order in which the vertices are removed, as a single line of \(n\) space-separated integers.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) \((1 \leq n \leq 10^5, 0 \leq m \leq 10^5)\), representing the number of vertices and edges, respectively. Following this, there are \(m\) lines. The \(i\)th line contains two integers \(u\) and \(v\) \((1 \leq u,v \leq n,\, u \neq v)\) denoting an undirected edge between vertices \(u\) and \(v\). The edges are labeled from \(1\) to \(m\) in the order they appear in the input.

outputFormat

Print a permutation of the vertices (\(n\) integers separated by spaces) representing the optimal vertex removal order that minimizes the lexicographical order of the isolated edges sequence.

sample

4 2
1 4
2 3

1 4 2 3