@SY

Поиск в ширину--2 (вершины идентифицируются названиями)

ограничение по времени на тест: 2 seconds
ограничение по памяти на тест: 64 megabytes

Напишите программу, которая будет реализовывать поиск в ширину в простом графе, вершины которого не нумерованы и идентифицируются словесными названиями.


Входные данные


В первой строке входных данных задано число NUM — количество различных поисков в ширину, которые нужно выполнить (на разных графах). Далее следуют NUM блоков, каждый из которых имеет следующую структуру.

Первая строка блока содержит целое число M — количество ребер графа. Далее следуют M строк, каждая из которых содержит по два названия — концы соответствующего ребра. Названия гарантированно не содержат пробелов и отделены друг от друга одним пробелом. Далее, в последней строке блока, записано единственное название — вершина, начиная с которой нужно запустить поиск (это название гарантированно хоть раз упоминалась как конец одного из ребер).

Количество различных графов в одном тесте NUM не превышает 5, количество рёбер в графе не превышает 50000.

Выходные данные


Выведите на стандартный выход (экран) NUM блоков, в каждом из которых записаны расстояния от указанной начальной вершины до всех достижимых (если есть недостижимые вершины, они вообще не упоминаются). Перечень должен быть отсортирован по названиям вершин, каждая пара (название, расстояние) должна выводиться в отдельной строке, блоки должны быть отделены друг от друга строкой «===» (три знака «равно»).


Примеры тестов


Входные данные
2
2
Cherk Zol
Cherk Sm
Zol
4
A Bb
Bb Ccc
Ccc A
Dddd Eeeee
Bb
Выходные данные
Cherk 1
Sm 2
Zol 0
===
A 1
Bb 0
Ccc 1

Примечание


Задачу можно решить, пользуясь map<string,int> и vector<string> для преобразований имен в номера и номеров в имена; тогда внутри программы можно использовать представление графа как vector<list<int> >. Для вывода в отсортированном порядке использовать прохождение по всем элементам от begin() до end() структуры map<string,int> (превращающей названия в номера).

Другой способ — вообще отказаться от нумерации вершин числами и представлять граф как map<string,list<string> >; в этом случае массивы, используемые самим поиском, следует заменить на map<string,int>.

0

@odip

Олимпиадная задача однако

0