# POI 2 Stage 3 Step Traversing a Tree ( DFS )

http://main.edu.pl/en/archive/oi/2/obc

In the first line of the standard input there is a positive integer n, not greater than 5000 - it is the number of vertices of the tree.
In each of the following n - 1 lines there is one pair of positive integers separated by a single space and representing one edge of the tree.

O( N )

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

const int MAXN = 5000;

int N;
vector< int > G[ MAXN ];

void dfs( int u, int fa, vector< int > &ans, int st ){
if( st ){
ans.push_back( u );
}
for( int i = 0; i < G[ u ].size(); ++i ){
int v = G[ u ][ i ];
if( v == fa ) continue;
dfs( v, u, ans, st ^ 1 );
}
if( not st ){
ans.push_back( u );
}
}

signed main(){
ios::sync_with_stdio( 0 );
cin >> N;
for( int i = 0; i < N - 1; ++i ){
int u, v; cin >> u >> v; --u, --v;
G[ u ].push_back( v );
G[ v ].push_back( u );
}
vector< int > ans;
dfs( 0, -1, ans, 0 );
assert( ans.size() == N );
for( int i = 0; i < N; ++i ){
cout << ans[ i ] + 1 << "\n";
}
return 0;
}
```