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

char data[] = "ABCD";
struct Edge {
    int to;
    int w;
};

const int M = 1000;
const int N = 100;

list<Edge> g[N];

void addEdge(int u, int v)
{
    g[u].push_back({v, 1});
}

bool vis[N];
void dfs(int u)
{
    cout << data[u] << ' ';
    vis[u] = true;
    for (auto it = g[u].begin(); it != g[u].end(); it ++)
    {
        if (!vis[it->to])
            dfs(it->to);
    }
}

bool inq[N];
void bfs(int u)
{
    queue<int> q;
    q.push(u);
    inq[u] = true;

    while (!q.empty())
    {
        int u1 = q.front();
        q.pop();
        cout << data[u1] << ' ';
        for (auto it = g[u1].begin(); it != g[u1].end(); it ++)
        {
            if (!inq[it->to])
            {
                q.push(it->to);
                inq[it->to] = true;
            }
        }
    }
}

int main()
{
    addEdge(0, 1);
    addEdge(0, 3);

    addEdge(1, 0);
    addEdge(1, 2);
    addEdge(1, 3);

    addEdge(2, 1);
    addEdge(2, 3);

    addEdge(3, 0);
    addEdge(3, 1);
    addEdge(3, 2);

    // 打印邻接表

    for (int u = 0; u < 4; u ++)
    {
        // 遍历链表 g[u]
        cout << u << "->";
        for (auto it = g[u].begin(); it != g[u].end(); it ++)
        {
            cout << it->to << ' ';
        }
        cout << endl;
    }

    dfs(0); // A B C D
    cout << endl;
    bfs(0); // A B D C

    return 0;
}