Школа программиста

1/12/2025, 4:17:50 AM 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Раздел империи

(Время: 2 сек. Память: 16 Мб Сложность: 38%)

Короли прошлого создали великую империю, в которой было N городов, и соединили их M двусторонними дорогами таким образом, что между любыми двумя городами существует путь, возможно через другие города. Одну и ту же пару городов может соединять несколько дорог, также дороги могут выходить и входить в один и тот же город. Со временем K городов усилились и возвысились над остальными, между ними начались междоусобицы. И однажды империя развалилась на K государств, столицей в каждом из которых стал усилившийся город.

До наших дней не дошло ни одной карты, где показывается, какой город оказался в каком государстве после того, как империя канула в лету. Однако известно, что в образованных государствах, также как и в великой империи, существовал путь между любой парой городов, возможно через другие города того же государства. И каждый город великой империи вошел в одно из государств, появившихся на ее руинах.

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

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

В первой строке входного файла INPUT.TXT записаны числа N (1 ≤ N ≤ 1000) и M (N-1 ≤ M ≤ 105) – количество городов и дорог соответственно. В следующих M строках идет описание дорог: каждая строка содержит два целых числа xi и yi (1 ≤ xi, yi ≤ N) – номера городов, соединенные дорогой.

В следующей строке записано целое число K (1 ≤ K ≤ N) – количество столиц. В последней строке перечислены K различных целых чисел ci (1 ≤ ci ≤ N) – номера столиц.

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

В выходной файл OUTPUT.TXT для каждого из K усилившихся городов в первой строке требуется вывести количество городов государства, чьей столицей стал этот город; во второй строке – номера городов, вошедших в государство.

Пример

INPUT.TXTOUTPUT.TXT
13 2
1 2
2 3
2
1 3
2
1 2
1
3

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Базовые понятия
 Представление графа
 Поиск в глубину
 Поиск в ширину
 A. Друзья
 B. Скачки
 C. Дерево
 D. Банкет
 E. Компоненты связности
 F. Удаление клеток
 G. Укладка плитки
 H. Раздел империи
 I. Покраска лабиринта
 J. Построение
 K. Рекурсия
 L. Производство деталей
 M. Доказательство теоремы
 N. Го
 O. Радио
 P. Конная прогулка

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru