DFS

#include <iostream>
using namespace std;

const int MAXN = 100;
int U[MAXN+1],Q[MAXN],P[MAXN],G[MAXN][MAXN] = {0},N, b,e;


int S[MAXN],top;
void make_empty(){top =-1;}
void push(int x){S[++top]=x;}
void pop(){top--;}
int look(){return S[top];}
bool not_empty(){return top>-1;}


void DFS (int r)
{  for(int i=1;i<=N;i++)
   U[i]=0;make_empty();
   push(r);U[r]=1;P[r]=0;
   while(not_empty())
   {  int t=look(); if(G[t][0]>0)
      { int v=G[t][G[t][0]--];
        if(!U[v]) { U[v]=1; P[v]=t; push(v); }
      }
      else pop();
   }
}

int main(){

    int x,y;

    while( cin >> x >> y ){
    G[x][++G[x][0]] = y;
    G[y][++G[y][0]] = x;
    }

    DFS(1);

    for(int i=1; i<=10; i++ ) cout << i << " " << P[i] << endl;
    /*for( int i=1; i<10; i++ ){
        for( int j=0; j<10; j++ ){
            cout << G[i][j] << "  ";
        }
        cout << endl;
    }*/

    return 0;
}