#include<iostream>
#include<vector>
#include<cstring>
#include<stack>
#include<cstdio>
 
#define max 1000
#define INF 100000000
using namespace std;
 
vector<int> adj[max];
int s[max],f[max],nodes[max];
int time_count,n,e;
char visited[max];
stack<int> st;
int tim,m=0;
 
void createAdjecenyList(int u,int v){
     adj[u].push_back(v);
       adj[v].push_back(u);
}
 
void print_st(stack<int> ps){
 while(!ps.empty()){
  printf("%d  ",ps.top());
  ps.pop();
 }
 printf("\n");
}
 
void printnodes(){
 int i;
 for(i=1;i<=n;i++)
  printf("node: %d   st_time: %d   end_time: %d\n",i,s[i],f[i]);
}
 
void dfs(int v){
//     int u,i,count;
	 tim = 0;
	 st.push(v);
     s[v] = tim++;
	 visited[v]=1;
	 while(!st.empty()) {
		printf("Printing stack: "); print_st(st);
		int u = st.top(); st.pop();
		f[u] = tim++;
//		nodes[m++]=u;
		for( int i=0; i<adj[u].size(); i++)
			if( !visited[adj[u][i]] ) {
				st.push(adj[u][i]);
                s[adj[u][i]] = tim++;
				visited[adj[u][i]] = 1;
			}
	}
} 
int main(){
    int u,v,i;
    memset(visited,0,sizeof(visited));  // 0  is for new node and 1 is for visited node
    scanf("%d",&n);  // number of nodes
    scanf("%d",&e); // number of edges
    while(e--) {
       scanf("%d %d",&u,&v);
       createAdjecenyList(u,v);
    }
    dfs(1);
    printnodes();
    cout<<endl;
    return 0;
}

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8Y3N0cmluZz4KI2luY2x1ZGU8c3RhY2s+CiNpbmNsdWRlPGNzdGRpbz4KIAojZGVmaW5lIG1heCAxMDAwCiNkZWZpbmUgSU5GIDEwMDAwMDAwMAp1c2luZyBuYW1lc3BhY2Ugc3RkOwogCnZlY3RvcjxpbnQ+IGFkalttYXhdOwppbnQgc1ttYXhdLGZbbWF4XSxub2Rlc1ttYXhdOwppbnQgdGltZV9jb3VudCxuLGU7CmNoYXIgdmlzaXRlZFttYXhdOwpzdGFjazxpbnQ+IHN0OwppbnQgdGltLG09MDsKIAp2b2lkIGNyZWF0ZUFkamVjZW55TGlzdChpbnQgdSxpbnQgdil7CiAgICAgYWRqW3VdLnB1c2hfYmFjayh2KTsKICAgICAgIGFkalt2XS5wdXNoX2JhY2sodSk7Cn0KIAp2b2lkIHByaW50X3N0KHN0YWNrPGludD4gcHMpewogd2hpbGUoIXBzLmVtcHR5KCkpewogIHByaW50ZigiJWQgICIscHMudG9wKCkpOwogIHBzLnBvcCgpOwogfQogcHJpbnRmKCJcbiIpOwp9CiAKdm9pZCBwcmludG5vZGVzKCl7CiBpbnQgaTsKIGZvcihpPTE7aTw9bjtpKyspCiAgcHJpbnRmKCJub2RlOiAlZCAgIHN0X3RpbWU6ICVkICAgZW5kX3RpbWU6ICVkXG4iLGksc1tpXSxmW2ldKTsKfQogCnZvaWQgZGZzKGludCB2KXsKLy8gICAgIGludCB1LGksY291bnQ7CgkgdGltID0gMDsKCSBzdC5wdXNoKHYpOwogICAgIHNbdl0gPSB0aW0rKzsKCSB2aXNpdGVkW3ZdPTE7Cgkgd2hpbGUoIXN0LmVtcHR5KCkpIHsKCQlwcmludGYoIlByaW50aW5nIHN0YWNrOiAiKTsgcHJpbnRfc3Qoc3QpOwoJCWludCB1ID0gc3QudG9wKCk7IHN0LnBvcCgpOwoJCWZbdV0gPSB0aW0rKzsKLy8JCW5vZGVzW20rK109dTsKCQlmb3IoIGludCBpPTA7IGk8YWRqW3VdLnNpemUoKTsgaSsrKQoJCQlpZiggIXZpc2l0ZWRbYWRqW3VdW2ldXSApIHsKCQkJCXN0LnB1c2goYWRqW3VdW2ldKTsKICAgICAgICAgICAgICAgIHNbYWRqW3VdW2ldXSA9IHRpbSsrOwoJCQkJdmlzaXRlZFthZGpbdV1baV1dID0gMTsKCQkJfQoJfQp9IAppbnQgbWFpbigpewogICAgaW50IHUsdixpOwogICAgbWVtc2V0KHZpc2l0ZWQsMCxzaXplb2YodmlzaXRlZCkpOyAgLy8gMCAgaXMgZm9yIG5ldyBub2RlIGFuZCAxIGlzIGZvciB2aXNpdGVkIG5vZGUKICAgIHNjYW5mKCIlZCIsJm4pOyAgLy8gbnVtYmVyIG9mIG5vZGVzCiAgICBzY2FuZigiJWQiLCZlKTsgLy8gbnVtYmVyIG9mIGVkZ2VzCiAgICB3aGlsZShlLS0pIHsKICAgICAgIHNjYW5mKCIlZCAlZCIsJnUsJnYpOwogICAgICAgY3JlYXRlQWRqZWNlbnlMaXN0KHUsdik7CiAgICB9CiAgICBkZnMoMSk7CiAgICBwcmludG5vZGVzKCk7CiAgICBjb3V0PDxlbmRsOwogICAgcmV0dXJuIDA7Cn0=

Ngo4CjEgMgoyIDMKMSAzCjEgNAoyIDQKMiA1CjMgNQozIDY=

6
8
1 2
2 3
1 3
1 4
2 4
2 5
3 5
3 6