#include <iostream>
#include <string>
#include <limits>
#include <vector>
#include <stdio.h>

using namespace std;

class adjlist;
class graph;
struct node {
	string name;
	int num_children = 0;
	string colour = "white";
	adjlist* children = NULL;
	node* next = NULL;
};
struct child_node {
	node* point;
	child_node* next = NULL;
	double distance;
	node* parent;
	double shortest;
	child_node* path_parent= NULL;
};
class adjlist {
private:
public:
	child_node* head;
	int paths;
	adjlist() {
		head = NULL;
		paths = 0;
	}

	void insert(node* city2, double distance, node* parent_path) {
		child_node* child = new child_node;
		child->point = city2;
		child->distance = distance;
		child->shortest = distance;
		child->parent = parent_path;
		if (head == NULL) {
			head = child;
			paths = paths + 1;
			return;
		}
		child_node* temp = head;
		if (temp->point == city2) {
			temp->distance = distance;
			return;
		}
		while (temp->next != NULL) {
			temp = temp->next;
			if (temp->point == city2) {
				temp->distance = distance;
				temp->shortest = distance;
				return;
			}
		}
		temp->next = child;
		paths = paths + 1;
	}

	void print() {
		if (head == NULL) {
			return;
		}
		child_node* temp = head;
		cout << temp->point->name;
		cout << temp->distance;
		while (temp->next != NULL) {
			temp = temp->next;
			cout << temp->point->name;
			cout << temp->distance;
		}
	}
};
class Graph {
private:
	int size;
public:
	node* head;
	Graph() {
		size = 0;
		head = NULL;
	}
	~Graph() {
		node* temp = head;
		node* nextup;
		if (head != NULL) {
			if (head->next == NULL) {
				delete nextup;
			}
			else {
				while (temp->next != NULL) {
					nextup = temp;
					temp = temp->next;
					delete nextup;
				}
			}
		}
		head = NULL;
		size = 0;
	}

	void insert(node* city) {
		if (head == NULL) {
			head = city;
			size = size + 1;
			return;
		}
		node* temp = head;
		while (temp->next != NULL) {
			temp = temp->next;
		}
		size = size + 1;
		temp->next = city;
	}

	node* find_key(string city_name) {
		if (head == NULL) {
			return NULL;
		}
		node* temp = head;
		if (temp->name == city_name) {
			return temp;
		}
		while (temp->next != NULL) {
			temp = temp->next;
			if (temp->name == city_name) {
				return temp;
			}
		}
		return NULL;
	}

	int return_size() {
		return size;
	}

};
class Heap {
private:
public:
	void insert(child_node* heap_array[], int index) {
		int temp = index + 1;
		int half;
		child_node* swap;
		while (temp > 1) {
			half = temp / 2;
			if (heap_array[temp - 1]->shortest < heap_array[half - 1]->shortest) {
				child_node* swap = heap_array[half - 1];
				heap_array[half - 1] = heap_array[temp - 1];
				heap_array[temp - 1] = swap;
			}
			temp = temp / 2;
		}

	}
	void relaxation(node* smallest, child_node* heap_array[], int& current_size, bool& already_found, int size, node*& found_distance, string city) {
		int index = size;
		node* temp = smallest;
		child_node* start = temp->children->head;
		child_node* current_min = heap_array[0];
		if (current_min->point->name == city) {
			found_distance = current_min->parent;
			already_found = true;
		}
		delete_min(heap_array, index, current_size, already_found);
		bool check = false;
		if (temp->children->head == NULL) {
			temp = smallest;
		}
		else {
			bool dupl = false;
			bool check = false;
			for (int i = 0; i < current_size; i++) {
				if (heap_array[i]->point == start->point) {
					if (current_min->shortest + start->shortest < heap_array[i]->shortest) {
						heap_array[i]->shortest = current_min->shortest + start->shortest;
						heap_array[i]->path_parent = current_min;
						insert(heap_array, i);
					}
					dupl = true;
				}
			}
			if (start->point->colour == "black") {
				check = true;
			}
			if (dupl == false && check == false) {
				heap_array[current_size] = start;
				heap_array[current_size]->path_parent = heap_array[0];
				current_size = current_size + 1;
				start->shortest = current_min->shortest + start->shortest;
				insert(heap_array, current_size-1);
			}
			dupl = false;
			check = false;
			while (start->next != NULL) {
				start = start->next;
				for (int i = 0; i < current_size; i++) {
					if (heap_array[i]->point == start->point) {
						if (current_min->shortest + start->shortest < heap_array[i]->shortest) {
							heap_array[i]->shortest = current_min->shortest + start->shortest;
							heap_array[i]->path_parent = current_min;
							insert(heap_array, i);
						}
						dupl = true;
					}
				}
				if (start->point->colour == "black") {
					check = true;
				}
				if (dupl == false && check == false) {
					heap_array[current_size] = start;
					heap_array[current_size]->path_parent = current_min;
					current_size = current_size + 1;
					start->shortest = current_min->shortest + start->shortest;
					insert(heap_array, current_size-1);
				}
				dupl = false;
				check = false;
			}
		}
		if (current_min->point->colour == "white") {
			current_min->point->colour = "black";
		}
	}
	void delete_min(child_node* heap_array[], int& index, int& current_size, bool& already_found) {
		heap_array[0] = heap_array[current_size - 1];
		heap_array[current_size - 1] = NULL;
		current_size = current_size - 1;
		child_node* l;
		child_node* r;
		child_node* previous;
		int cycle = 1;
		while (cycle <= current_size) {
			previous = heap_array[cycle - 1];
			if (heap_array[cycle*2- 1] || cycle * 2 > current_size) {
				break;
			}
			heapify(heap_array, index, current_size, already_found, cycle);
			l = heap_array[(cycle * 2) - 1];
			r = heap_array[cycle * 2];
			if (previous == l) {
				cycle = cycle * 2;
			}
			else if (previous == r) {
				cycle = cycle * 2 + 1;
			}
			else {
				break;
			}
		}

	}
	void heapify(child_node* heap_array[], int& index, int& current_size, bool& already_found, int half) {
		int left = half * 2;
		int right = (half * 2) + 1;
		if (heap_array[left - 1] == NULL || left > current_size) {
			return;
		}
		else if (heap_array[right - 1] == NULL) {
			if (heap_array[half - 1]->shortest > heap_array[left - 1]->shortest) {
				child_node* swap = heap_array[left - 1];
				heap_array[left - 1] = heap_array[half - 1];
				heap_array[half - 1] = swap;
				heapify(heap_array, index, current_size, already_found, left);
			}
			return;
		}
		else {
			//which one is smaller
			if (heap_array[left - 1]->shortest < heap_array[right - 1]->shortest) {
				if (heap_array[left - 1]->shortest < heap_array[half - 1]->shortest) {
					child_node* swap = heap_array[left - 1];
					heap_array[left - 1] = heap_array[half - 1];
					heap_array[half - 1] = swap;
					heapify(heap_array, index, current_size, already_found, left);
				}
			}
			else if (heap_array[right - 1]->shortest < heap_array[left - 1]->shortest) {
				if (heap_array[right - 1]->shortest < heap_array[half - 1]->shortest) {
					child_node* swap = heap_array[right - 1];
					heap_array[right - 1] = heap_array[half - 1];
					heap_array[half - 1] = swap;
					heapify(heap_array, index, current_size, already_found, right);
				}
			}
			else {
				// even
				if (heap_array[left - 1]->shortest < heap_array[half - 1]->shortest) {
					child_node* swap = heap_array[left - 1];
					heap_array[left - 1] = heap_array[half - 1];
					heap_array[half - 1] = swap;
					heapify(heap_array, index, current_size, already_found, left);
				}
			}
		}
	}

	void create(node* start, child_node* heap_array[], int& index, int& current_size, bool& already_found) {
		child_node* temp = start->children->head;
		heap_array[index] = temp;
		start->colour = "black";
		index = index + 1;
		current_size = current_size + 1;
		while (temp->next != NULL) {
			temp = temp->next;
			heap_array[index] = temp;
			current_size = current_size + 1;
			index = index + 1;
		}
		int half = current_size / 2;
		for (int i = half + 1; i >= 1; i = i -1) {
			heapify(heap_array, index, current_size, already_found, i);
		}
	}
	void print(child_node* heap_array[], int size) {
		if (heap_array[0] == NULL) {
			return;
		}
		for (int i = 0; i < size; i++) {
			if (heap_array[i] != NULL) {
				cout << heap_array[i]->point->name << " " << heap_array[i]->shortest<< endl;
			}
		}
	}
};
	void search(node* start, int size, string name, node* BFsearch[], int& index, int& position, bool& already_found) {
		node* temp = start;
		if (temp->name == name) {
			cout << "found " << name << endl;
			already_found = true;
			return;
		}
		BFsearch[index] = temp;
		index = index + 1;
		if (temp->num_children == 0) {
			return;
		}
		bool dupl = false;
		child_node* cycle = temp->children->head;
		BFsearch[index] = cycle->point;
		index = index + 1;
		while (cycle->next != NULL){
			cycle = cycle->next;
			for (int i = 0; i < index; i++) {
				if (BFsearch[i] == cycle->point) {
					bool dupl = true;
				}
			}
			if (dupl == false) {
				BFsearch[index] = cycle->point;
				index = index + 1;
			}
			dupl = false;
		}
		int new_pos = position + 1;
		if (new_pos > size) {
			return;
		}
		if (BFsearch[new_pos] != NULL) {
			search(BFsearch[new_pos], size, name, BFsearch, index, new_pos, already_found);
		}
	}


int main() {
	string input = "";
	vector<string> information;
	vector<string> names;
	Graph my_graph;
	while (1) {
		cin >> input;
		if (input == "i") {
			cin >> input;
			string current = "";
			for (int i = 0; i < input.length(); i++) {
				current = current + input[i];
				if (i == input.length() - 1) {
					break;
				}
			}
			bool duplicate = false;
			for (int i = 0; i < names.size(); i++) {
				if (names[i] == current) {
					cout << "failure" << endl;
					duplicate = true;
				}
			}
			if (duplicate == true) {
				continue;
			}
			node* city = new node;
			adjlist* children1 = new adjlist;
			city->children = children1;
			city->name = current;
			my_graph.insert(city);
			cout << "success" << endl;
			names.push_back(current);
		}

		else if (input == "setd") {
			cin >> input;
			string current = "";
			for (int i = 0; i < input.length(); i++) {
				if (input[i] == ';') {
					information.push_back(current);
					current = "";
					continue;
				}
				current = current + input[i];
				if (i == input.length() - 1) {
					information.push_back(current);
				}
			}
			int missing = 0;
			string city1 = information[0];
			string city2 = information[1];
			double distance = stod(information[2]);
			for (int i = 0; i < names.size(); i++) {
				if (names[i] == city1 || names[i] == city2) {
					missing = missing + 1;
				}
			}
			if (missing != 2) {
				cout << "failure" << endl;
			}
			else {

				cout << "success" << endl;
				node* first = my_graph.find_key(city1);
				node* second = my_graph.find_key(city2);
				first->children->insert(second, distance, first);
				second->children->insert(first, distance, second);
				first->num_children = 1;
				second->num_children = 1;
			}
			information.clear();
		}

		else if (input == "s") {
			cin >> input;
			int size = my_graph.return_size();
			string current = "";
			for (int i = 0; i < input.length(); i++) {
				current = current + input[i];
				if (i == input.length() - 1) {
					break;
				}
			}
			node* BFsearch[size];
			for (int i = 0; i < size; i++) {
				BFsearch[i] = NULL;
			}
			int index = 0;
			int position = 0;
			if (my_graph.head == NULL) {
				cout << "not found" << endl;
			}
			else {
				node* start = my_graph.head;
				bool already_found = false;
				while (start != NULL) {
					search(start, size, current, BFsearch, index, position, already_found);
					if (already_found == true) {
						break;
					}
					index = 0;
					position = 0;
					start = start->next;
					node* BFsearch[size];
					for (int i = 0; i < size; i++) {
						BFsearch[i] = NULL;
					}
				}
				if (already_found == false) {
					cout << "not found" << endl;
				}
			}
		}
		else if (input == "graph_nodes") {
			int size = my_graph.return_size();
			cout << "number of nodes " << size << endl;
		}
		else if (input == "graph_edges") {
			int total = 0;

			if (my_graph.head == NULL) {
				cout << "number of edges " << total << endl;
			}
			else {
				node* start = my_graph.head;
				if (start->children != NULL) {
					total = total + start->children->paths;
				}
				while (start->next != NULL) {
					start = start->next;
					if (start->children != NULL) {
						total = total + start->children->paths;
					}
				}
				total = total / 2;
				cout << "number of edges " << total << endl;
			}
		}
		else if (input == "degree") {
			cin >> input;
			string current = "";
			for (int i = 0; i < input.length(); i++) {
				current = current + input[i];
				if (i == input.length() - 1) {
					break;
				}
			}
			node* start = my_graph.head;
			if (start->name == current) {
				cout << "degree of " << current << " " << start->children->paths << endl;
			}
			else {
				while (start->next != NULL) {
					start = start->next;
					if (start->name == current) {
						cout << "degree of " << current << " " << start->children->paths << endl;
					}
				}
			}
		}
		else if (input == "d") {
			cin >> input;
			string current = "";
			string city1;
			string city2;
			for	(int i = 0; i < input.length(); i++) {
				if (input[i] == ';') {
					city1 = current;
					current = "";
					continue;
				}
				current = current + input[i];
				if (i == input.length() - 1) {
					city2 = current;
				}
			}
			double distance = 0;
			bool city2_found = false;
			node* first = my_graph.find_key(city1);
			if (city2 == city1) {
				cout << "direct distance " << city1 << " to " << city1 << " " << distance << endl;
				city2_found = true;
			}
			else if (first == NULL) {
				cout << "failure" << endl;
			}
			else{
				child_node* start = first->children->head;
				if (start == NULL) {
					cout << "failure" << endl;
				}
				else {
					if (start->point->name == city2) {
						cout << "direct distance " << city1 << " to " << city2 << " " << start->distance << endl;
						city2_found = true;
					}
					while (start->next != NULL) {
						start = start->next;
						if (start->point->name == city2) {
							cout << "direct distance " << city1 << " to " << city2 << " " << start->distance << endl;
							city2_found = true;
						}
					}
					if (city2_found == false) {

						cout << "failure" << endl;
					}
				}
			}
		}
		else if (input == "shortest_d") {
			cin >> input;
			string current = "";
			string city1;
			string city2;
			for (int i = 0; i < input.length(); i++) {
				if (input[i] == ';') {
					city1 = current;
					current = "";
					continue;
				}
				current = current + input[i];
				if (i == input.length() - 1) {
					city2 = current;
				}
			}
			//check existence
			double distance = 0;
			bool city2_found = false;
			int index = 0;
			int current_size = 0;
			int size = my_graph.return_size();
			node* first = my_graph.find_key(city1);
			if (city2 == city1) {
				cout << "shortest distance " << city1 << " to " << city1 << " " << distance << endl;
				city2_found = true;
			}
			else if (first == NULL) {
				cout << "failure" << endl;
			}
			else {
				child_node* start = first->children->head;
				if (start == NULL) {
					cout << "failure" << endl;
				}
				else {
					if (city2_found == false) {
						child_node* heap_array[size];
						for (int i = 0; i < size; i++) {
							heap_array[i] = NULL;
						}
						Heap my_heap;
						node* found_distance = NULL;
						my_heap.create(first, heap_array, index, current_size, city2_found);

						while(current_size >= 1){
							node* pass = heap_array[0]->point;
							my_heap.relaxation(pass, heap_array, current_size, city2_found, size, found_distance, city2);
						}
						if (found_distance != NULL) {
							child_node* start = found_distance->children->head;
							while (start != NULL) {
								if (start->point->name == city2) {
									cout << "shortest distance " << city1 << " to " << city2 << " " << start->shortest << endl;
									city2_found = true;
								}
								start = start->next;
							}
						}
						else {
							cout << "failure" << endl;
						}
					}
				}
			}
			//reset
			node* start = my_graph.head;
			while (start != NULL) {
				start->colour = "white";
				child_node* copyback = start->children->head;
				while (copyback != NULL) {
					copyback->path_parent = NULL;
					copyback->shortest = copyback->distance;
					copyback = copyback->next;
				}
				start = start->next;
			}
		}
		else if (input == "print_path") {
			cin >> input;
			string current = "";
			string city1;
			string city2;
			for (int i = 0; i < input.length(); i++) {
				if (input[i] == ';') {
					city1 = current;
					current = "";
					continue;
				}
				current = current + input[i];
				if (i == input.length() - 1) {
					city2 = current;
				}
			}

			double distance = 0;
			bool city2_found = false;
			int index = 0;
			int current_size = 0;
			int size = my_graph.return_size();
			node* first = my_graph.find_key(city1);
			if (city2 == city1) {
				cout << "shortest distance " << city1 << " to " << city1 << " " << distance << endl;
				city2_found = true;
			}
			else if (first == NULL) {
				cout << "failure" << endl;
			}
			else {
				child_node* start = first->children->head;
				if (start == NULL) {
					cout << "failure" << endl;
				}
				else {
					if (city2_found == false) {
						child_node* heap_array[size];
						for (int i = 0; i < size; i++) {
							heap_array[i] = NULL;
						}
						Heap my_heap;
						node* found_distance = NULL;
						my_heap.create(first, heap_array, index, current_size, city2_found);

						while (current_size >= 1) {
							node* pass = heap_array[0]->point;
							my_heap.relaxation(pass, heap_array, current_size, city2_found, size, found_distance, city2);
						}
						if (found_distance != NULL) {
							node* citypath[size];
							for (int i = 0; i < size; i++) {
								citypath[i] = NULL;
							}
							int cycle = 0;
							child_node* start = found_distance->children->head;
							while (start != NULL) {
								if (start->point->name == city2) {
									city2_found = true;
									break;
								}
								start = start->next;
							}
							citypath[cycle] = start->point;
							cycle = cycle + 1;
							//path print
							while (start->path_parent != NULL) {
								citypath[cycle] = start->path_parent->point;
								cycle = cycle + 1;
								if (start->path_parent == NULL) {
									break;
								}
								start = start->path_parent;
							}
							citypath[cycle] = start->parent;
							string current = "";
							for (int i = size-1; i >= 0; i--) {
								if (citypath[i] != NULL) {
									current = current + citypath[i]->name + " ";
								}
							}
							cout << current << endl;
						}
						else {
							cout << "failure" << endl;
						}
					}
				}
			}
			//reset
			node* start = my_graph.head;
			while (start != NULL) {
				start->colour = "white";
				child_node* copyback = start->children->head;
				while (copyback != NULL) {
					copyback->path_parent = NULL;
					copyback->shortest = copyback->distance;
					copyback = copyback->next;
				}
				start = start->next;
			}
		}
		else if (input == "clear") {
			my_graph.~Graph();
			names.clear();
			cout << "success" << endl;
		}

		if (cin.eof()) {
			break;
		}
	}
	return 0;
}