Problem Statement

Farmer John has N farms (2 ≤ N ≤ 10^4) connected by M roads (1 ≤ M ≤ 5×10^4). Multiple roads between the same pair of farms are allowed.

Bassie starts patrolling from farm 1. Every road must be traversed exactly once in each direction, and the path must end back at farm 1.

Output any valid sequence of farms that satisfies the requirement. It is guaranteed that such a path exists.

Input Format

The first line contains two integers N and M. The next M lines each contain two integers u and v, representing a road between farms u and v.

Output Format

Output the visited farms, one per line.

Example

Input

4 5
1 2
1 4
2 3
2 4
3 4

Output

1
2
3
4
2
1
4
3
2
4
1

Solution Explanation

This problem is a direct application of an Eulerian circuit. An Eulerian circuit is a path that traverses every edge exactly once and returns to the starting vertex. Here, each road must be traversed twice (once in each direction), which is equivalent to converting every undirected edge into two directed edges. This transformation guarantees that all vertices will have equal in‑degree and out‑degree, ensuring an Eulerian circuit exists starting from farm 1.

Approach

We can find the circuit using a depth‑first search that removes edges as they are visited (Hierholzer's algorithm). To avoid recursion depth issues for large graphs, we can simulate the traversal with an explicit stack.

Below is an implementation that builds the circuit and outputs the farm visit order.

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 10005;
vector<int> adj[MAX_N];
vector<int> tour;

void findCircuit(int start) {
    stack<int> stk;
    stk.push(start);
    while (!stk.empty()) {
        int cur = stk.top();
        if (!adj[cur].empty()) {
            int nxt = adj[cur].back();
            adj[cur].pop_back();
            stk.push(nxt);
        } else {
            tour.push_back(cur);
            stk.pop();
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    findCircuit(1);
    reverse(tour.begin(), tour.end());
    for (int farm : tour) {
        cout << farm << '\n';
    }
    return 0;
}

The algorithm starts at farm 1, follows available edges until reaching a dead end, backtracks, and collects the vertices in reverse order. Reversing the collected list gives a valid patrol route.

Key Concepts

• Eulerian path / circuit: A trail visiting every edge exactly once. Existence conditions depend on vertex degrees and graph connectivity.
• Hierholzer's algorithm: A linear‑time method to construct Eulerian circuits by merging sub‑circuits.
• Stack simulation: Replaces recursion to handle deep graphs without stack overflow.

For the Watchcow problem, no explicit connectivity or degree checks are needed because a solution is guaranteed.