#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

unordered_map<string,vector<string>> G; // the adjacency list
unordered_map<string,bool> visited;

void Tokenize(string line, vector<string> & tokens, string delimiters){
        string token = "";
        string OneCharString = " ";
        for (int i=0; i<line.size(); i++)
                if (find(delimiters.begin(), delimiters.end(), line[i])!=delimiters.end()) // line[i] is one of the delimiter characters
                {
                        if (token != "")
                                tokens.push_back(token);
                        token = "";
                }
                else
                {
                        OneCharString[0] = line[i];
                        token +=OneCharString;
                }

        if (token != "")
                tokens.push_back(token);
}

void readGreaph(char* file_name){
	fstream inf;
	inf.open(file_name);

	string line;
	while (getline(inf,line).good()){
		vector<string> tokens;
		Tokenize(line, tokens, " \t");	
		if (tokens.size()!=2)
			continue;
		G[tokens[0]].push_back(tokens[1]);
		G[tokens[1]].push_back(tokens[0]);
	}
	inf.close();
}

// assuming that nodes have unique string identifiers
void DFS(string v, vector<string>& ret){
	visited[v] = true;
	ret.push_back(v);
	for (int i=0; i< G[v].size(); i++){
		if (!visited[G[v][i]])
			DFS(G[v][i], ret);
	}	
}

vector<string> BFS(string v){
        vector<string> ret;

	queue<string> q;
	q.push(v);	
        visited[v] = true;
	while (!q.empty()){
	        string u = q.front();
		q.pop();

		ret.push_back(u);
        	for (int i=0; i< G[u].size(); i++){
			if (visited[G[u][i]])
				continue;
			q.push(G[u][i]);
			visited[G[u][i]] = true;
        	}
	}
        return ret;
}

int main(int argc, char** argv){
	readGreaph(argv[1]);

	
	cout << "DFS:" << endl;
        vector<string> output; 
	DFS(argv[2], output);
        for (int i=0; i<output.size(); i++)
                cout << output[i] << endl;

	visited.clear();

	cout << "BFS:" << endl;
	output = BFS(argv[2]);
	for (int i=0; i<output.size(); i++)
		cout << output[i] << endl;
}