Problem Description

You are given a connected undirected graph with \(N\\) vertices and \(M\\) edges. The vertices are numbered from \(1\\) to \(N\\), and the given graph does not contain any multiple edges or self-loops.

Output a permutation \(p\\) of length \(N\\) that satisfies the following conditions:

• For each \(1 \\leq i \\leq N\\), the distance \(D(i, p\_i)\\) between vertices \(i\\) and \(p\_i\\) is either 1 or 2.

It can be proven that such a permutation always exists. If there are multiple valid permutations, you may output any one of them.

The distance \(D(u, v)\\) between two vertices \(u\\) and \(v\\) is defined as the minimum number of edges in a path from vertex \(u\\) to vertex \(v\\) in the graph.

Input Format

The input is given from the standard input in the following format:

```
\(N\) \(M\)
\(u_1\) \(v_1\)
\(u_2\) \(v_2\)
\(\vdots\)
\(u_M\) \(v_M\)

## Output Format

Output the permutation \\(p\\) that satisfies the conditions, separated by spaces.

## Sample Input and Output

### Sample Input #1

2 1
1 2

### Sample Output #1

2 1

### Sample Input #2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

### Sample Output #2

2 3 4 1
```

Notes/Hints

Constraints

• \(2 \\leq N \\leq 200000\\)
• \(N-1 \\leq M \\leq 200000\\)
• \(1 \\leq u\_i, v\_i \\leq N\\) (\(1 \\leq i \\leq M)\\)
• The given graph is connected and does not contain any multiple edges or self-loops.
• All input values are integers.

Sample Explanation 1

The distance between the two vertices is \(D(1, 2) = D(2, 1) = 1\\), which satisfies the condition.

Sample Explanation 2

If there are multiple possible answers, any one of them will be considered correct.

见题面 Input 部分

见题面 Output 部分