#include <bits/stdc++.h>
using namespace std;
struct node{
int data;
node* next;
node(){
data = 0;
next = NULL;
}
node(int GivenData){
data = GivenData;
next = NULL;
}
};
struct LinkedList{
node* head;
LinkedList(){
head = NULL;
}
void push_back(int data){
node* new_node = new node(data);
if (head == NULL) {
head = new_node;
return;
}
node* temp = head;
while(temp->next != NULL) {
temp = temp->next;
}
temp->next = new_node;
}
void print(){
node* temp = head;
while(temp != NULL){
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
const int N = 100;
LinkedList adj[N];
vector<int>vis(N);
void dfs(int now){
vis[now] = 1;
node* tmp = adj[now].head;
cout << now << " ";
while(tmp != NULL){
if(vis[tmp->data] == 0) dfs(tmp->data);
tmp = tmp->next;
}
}
int main(){
int n; cin >> n;
int m; cin >> m;
for(int i = 0; i < m; i++){
int a,b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
cout << "DFS Traversal of the given graph is: ";
dfs(1);
cout << endl;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3Qgbm9kZXsKICAgIGludCBkYXRhOwogICAgbm9kZSogbmV4dDsKICAgIG5vZGUoKXsKICAgICAgICBkYXRhID0gMDsKICAgICAgICBuZXh0ID0gTlVMTDsKICAgIH0KICAgIG5vZGUoaW50IEdpdmVuRGF0YSl7CiAgICAgICAgZGF0YSA9IEdpdmVuRGF0YTsKICAgICAgICBuZXh0ID0gTlVMTDsKICAgIH0KfTsKCnN0cnVjdCBMaW5rZWRMaXN0ewogICAgbm9kZSogaGVhZDsKICAgIExpbmtlZExpc3QoKXsgCiAgICAgICAgaGVhZCA9IE5VTEw7CiAgICB9CiAgICB2b2lkIHB1c2hfYmFjayhpbnQgZGF0YSl7CiAgICAgICAgbm9kZSogbmV3X25vZGUgPSBuZXcgbm9kZShkYXRhKTsKICAgICAgICBpZiAoaGVhZCA9PSBOVUxMKSB7CiAgICAgICAgICAgIGhlYWQgPSBuZXdfbm9kZTsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0gCiAgICAgICAgbm9kZSogdGVtcCA9IGhlYWQ7CiAgICAgICAgd2hpbGUodGVtcC0+bmV4dCAhPSBOVUxMKSB7CiAgICAgICAgICAgIHRlbXAgPSB0ZW1wLT5uZXh0OwogICAgICAgIH0KICAgICAgICB0ZW1wLT5uZXh0ID0gbmV3X25vZGU7CiAgICB9CiAgICB2b2lkIHByaW50KCl7CiAgICAgICAgbm9kZSogdGVtcCA9IGhlYWQ7CiAgICAgICAgd2hpbGUodGVtcCAhPSBOVUxMKXsKICAgICAgICAgICAgY291dCA8PCB0ZW1wLT5kYXRhIDw8ICIgIjsKICAgICAgICAgICAgdGVtcCA9IHRlbXAtPm5leHQ7CiAgICAgICAgfQogICAgICAgIGNvdXQgPDwgZW5kbDsKICAgIH0KfTsKY29uc3QgaW50IE4gPSAxMDA7CkxpbmtlZExpc3QgYWRqW05dOwp2ZWN0b3I8aW50PnZpcyhOKTsKCnZvaWQgZGZzKGludCBub3cpewogICAgdmlzW25vd10gPSAxOwogICAgbm9kZSogdG1wID0gYWRqW25vd10uaGVhZDsKICAgIGNvdXQgPDwgbm93IDw8ICIgIjsKICAgIHdoaWxlKHRtcCAhPSBOVUxMKXsKICAgICAgICBpZih2aXNbdG1wLT5kYXRhXSA9PSAwKSBkZnModG1wLT5kYXRhKTsKICAgICAgICB0bXAgPSB0bXAtPm5leHQ7CiAgICB9Cn0KCmludCBtYWluKCl7CiAgICBpbnQgbjsgY2luID4+IG47CiAgICBpbnQgbTsgY2luID4+IG07CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbTsgaSsrKXsKICAgICAgICBpbnQgYSxiOwogICAgICAgIGNpbiA+PiBhID4+IGI7CiAgICAgICAgYWRqW2FdLnB1c2hfYmFjayhiKTsKICAgICAgICBhZGpbYl0ucHVzaF9iYWNrKGEpOwogICAgfQogICAgY291dCA8PCAiREZTIFRyYXZlcnNhbCBvZiB0aGUgZ2l2ZW4gZ3JhcGggaXM6ICI7CiAgICBkZnMoMSk7CiAgICBjb3V0IDw8IGVuZGw7Cn0K