Таня почти уже вышла из дома, чтобы идти в школу, когда раздался звонок. Звонила завуч, сказала, что сегодня первые три урока не состоятся — в школе нет электричества. Таня — староста своего класса, и завуч просила передать всему классу эту новость.

— Что же теперь делать? Времени-то практически не осталось — подумала Таня. — Ну ладно, сейчас я позвоню Лене, потом Кате, потом Маше. А Лена в это время пусть звонит Вите, она знает его телефон, а Витя пусть позвонит Маше. Нет, Маше же я сама позвоню — пусть лучше он звонит Мише. А Катя пусть позвонит Наташе... Нет, так не получится, они же вчера поссорились. Так, некогда размышлять, надо скорее звонить Лене, авось все в конце концов узнают...

С горем пополам Таня все-таки смогла разослать новость по классу, причем получилось так, что до нескольких человек новость дошла слишком поздно, а многим позвонило, сообщая новость, сразу несколько человек. В итоге, класс в целом понес ощутимые моральные (опоздания) и материальные (лишние расходы на телефон) потери. Вечером Таня решила для подобных случаев заранее придумать план звонков, и не пускать больше такие оповещения на самотек, не зря же ее назначили старостой класса... Но задача оказалась непростой.

Помогите Тане составить такой план звонков, с помощью которого удастся разнести новость по классу как можно скорее. При этом все ученики должны получить сообщение, но ни один не должен получить его более одного раза. Передача новости по телефону занимает ровно одну минуту. В начальный момент времени новость знает только староста.

Для решения задачи Таня выписала список всех учеников, а так же для каждого ученика список тех учеников, кому он может позвонить. Можно считать, что если Маша может позвонить Кате, то и Катя может позвонить Маше (даже если в составленном Таней списке указана только одна из этих связей). Можно также предполагать, что по такому "сарафанному радио" сообщение может дойти до любого ученика класса.

Первая строка содержит количество учеников в классе N (1 ≤ N ≤ 10). Вторая строка содержит целое число M (0 ≤ M ≤ 45). Каждая из следующих M строк содержит пару имен одноклассников, которые могут звонить друг другу, разделенных пробелом. Последняя строка содержит имя старосты. Все имена учеников различны, и состоят не более, чем из 20 заглавных и прописных латинских букв.

В первой строке — время в минутах, необходимое для передачи новости всему классу согласно предлагаемому плану. Далее выводится описание плана звонков. Звонки идущие параллельно следует объединить в группу. Группы следует упорядочить по времени. Описание каждой группы начинается со строки, содержащей количество звонков. Каждый звонок описывается в отдельной строке. Описание звонка состоит из пары имен (кто звонит, кому звонит), записанной через пробел.