#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>

#define Maxsize 50

using namespace std;

// DFS和BFS要用到的辅助数组
bool visitD[Maxsize];
bool visitB[Maxsize];

// 边表结点定义
typedef struct ArcNode
{
    int value; // 结点的值
    struct ArcNode *next; // 指向下一条边的指针
}ArcNode;

// 顶点表结点定义
typedef struct VNode
{
    int data; // 顶点信息
    ArcNode *firstarc; // 指向第一条依附于这条边的指针
}VNode, AdjList[Maxsize];

// 邻接表定义
typedef struct
{
    AdjList vertices; //邻接表
    int vexnum, arcnum; // 图的顶点数和边数
}ALGraph, *Graph;


//  辅助队列定义
typedef struct
{
    int data[Maxsize];
    int front, rear;
}SqQueue;

// 将边b加到a的后面
void AddAB(Graph &A, int a, int b)
{
    ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode)); 
    p ->value = b;
    p ->next = NULL;

    if(A ->vertices[a].firstarc == NULL)
        A ->vertices[a].firstarc = p;
    else 
    {
        p ->next = A ->vertices[a].firstarc;
        A ->vertices[a].firstarc = p;
    }
}

// 邻接表的初始化 
void InitAlGraph(Graph &A)
{
    int n, m;
    cin >> n >> m; // 共n个结点, m条边

    A = (ALGraph *)malloc(sizeof(ALGraph));
    A ->vexnum = n;
    A ->arcnum = m;

    for(int i = 1; i <= n; i ++) // 建立n个顶点
    {
        int x;
        cin >> x;
        A ->vertices[i].data = x; // 引用指针下的变量要用“->”，其余（如数组）下的变量用"."即可
        A ->vertices[i].firstarc = NULL;
    }

    for(int i = 0; i < m; i ++) // 建立m条边
    {
        int a, b;
        cin >> a >> b;
        // 无向图，先将b加到a后面
        AddAB(A, a, b);

        // 再将b加到a后面
        AddAB(A, b, a);
    }
}

// 队列的初始化
void InitQueue(SqQueue &Q)
{
    Q.front = Q.rear = 0;
}

// 判断队列是否为空
bool isEmpty(SqQueue Q)
{
    if(Q.front == Q.rear)
        return true;

    return false;
}

//队列添加元素
bool EnQueue(SqQueue &Q, int x)
{
    if((Q.rear + 1) % Maxsize == Q.front) // 队列已满
        return false;

    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % Maxsize;
    return true;
}

//队列删除元素(将x带回去)
bool DeQueue(SqQueue &Q, int &x)
{
    if(Q.front == Q.rear) // 队列为空
        return false;

    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % Maxsize;

    return true;
}

// 访问x结点
void visit(Graph G, int x)
{
    cout << G ->vertices[x].data << ' ';
}

// BFS过程
void BFS(SqQueue &Q, Graph G, int x)
{
    visit(G, x);
    visitB[x] = true;
    EnQueue(Q, x);
    while(!isEmpty(Q))
    {
        int a = -1;
        DeQueue(Q, a);
        for(ArcNode *p = G ->vertices[a].firstarc; p; p = p ->next)
        {
            int w = p ->value;
            if(visitB[w] == false)
            {
                visit(G, w);
                visitB[w] = true;
                EnQueue(Q, w);
            }
        }
    }
}

// 广度优先搜索
void BFSTraverse(Graph G)
{
    for(int i = 1 ; i <= G ->vexnum; i ++)
        visitB[i] = false;

    SqQueue Q;    
    InitQueue(Q); // 初始化辅助队列
    for(int i = 1; i <= G ->vexnum; i ++) // 从1号节点开始遍历 
        if(!visitB[i])
            BFS(Q, G, i);
}


// DFS过程
void DFS(SqQueue &Q, Graph G, int x)
{
    visit(G, x);
    visitD[x] = true;

    for(ArcNode *p = G ->vertices[x].firstarc; p; p = p ->next)
    {
        int w = p ->value;
        if(!visitD[w])
            DFS(Q, G, w);
    }
}


// 深度优先搜索
void DFSTraverse(Graph G)
{
    for(int i = 1 ; i <= G ->vexnum; i ++)
        visitB[i] = false;

    SqQueue Q;    
    InitQueue(Q); // 初始化辅助队列
    for(int i = 1; i <= G ->vexnum; i ++) // 从1号节点开始遍历 
        if(!visitD[i])
            DFS(Q, G, i);
}

int main()
{
    Graph A;
    InitAlGraph(A);

    // cout << A ->vertices[1].data << endl;
    // cout << A ->vertices[3].firstarc ->value << endl;
    // cout << A ->vertices[3].firstarc ->next ->value << endl;
    // cout << A ->vertices[3].firstarc ->next ->next ->value;

    cout << "该图的广度优先遍历序列为";
    BFSTraverse(A);
    cout << endl;

    cout << "该图的深度优先遍历序列为";
    DFSTraverse(A);
    cout << endl;

    return 0;
}