#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<queue>

#include<stack>

#include<algorithm>

#define MAX 1000

using namespace std;

int head[MAX],ans;

int vis[MAX],viss[MAX];

int map[MAX],ant;

queue<int>q;

struct node

{

	int u,v,next;

}edge[MAX];

void init()

{

	memset(head,-1,sizeof(head));

	ans=0;

}

void add(int u,int v)

{

	edge[ans].u=u;

	edge[ans].v=v;

	edge[ans].next=head[u];

	head[u]=ans++;

}

void bfs(int beg)

{

	int i,j;

	vis[beg]=1;

	q.push(beg);

	printf("%d ",beg);

	while(!q.empty())

	{

		int u=q.front();

		q.pop();

		for(i=head[u];i!=-1;i=edge[i].next)

		{

			int v=edge[i].v;

			if(!vis[v])

			{

				printf("%d ",v);

				vis[v]=1;

				q.push(v);

			}

		}

	}

	printf("\n");

}

void dfs(int beg)

{

	int i,j;

	vis[beg]=1;

	if(!viss[beg])

	{

		map[ant++]=beg;

		viss[beg]=1;

	}

	for(i=head[beg];i!=-1;i=edge[i].next)

	{

		int v=edge[i].v;

		if(!vis[v])

		{

			if(!viss[v])

			{

				map[ant++]=v;

				viss[v]=1;

			}

			vis[v]=1;

			dfs(v);

			vis[v]=0;

		}

	}

}

int main()

{

	int n,m,j,i,k,a,b;

	int start;

	while(1)

	{

		init();

		printf("请输入你要创建的图的顶点连线的对数\n");

		scanf("%d",&n);

		printf("请输入每对顶点的值\n");

		while(n--)

		{

			scanf("%d%d",&a,&b);

			add(a,b);

			add(b,a);

		}

		while(1)

		{

			printf("请输入你要开始广度优先遍历的起点,如果你想要退出进行其他操作请输入-1\n");

		    memset(vis,0,sizeof(vis));

			while(!q.empty())

			    q.pop();

			scanf("%d",&start);

		    if(start==-1)

			    break;

		    bfs(start);

		}

		while(1)

		{

			printf("请输入你要开始深度优先遍历的起点,如果你想要退出进行其他操作请输入-1\n");

		    memset(vis,0,sizeof(vis));

		    memset(viss,0,sizeof(viss));

			while(!q.empty())

			    q.pop();

			scanf("%d",&start);

		    if(start==-1)

			    break;

			ant=0;

		    dfs(start);

		    for(i=0;i<ant;i++)

		    {

		    	if(map[i]!=map[i+1])

		    	printf("%d ",map[i]);

		    }

		    printf("\n");

		}

	}

	return 0;

}