Короли прошлого создали великую империю, в которой было 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.TXT
OUTPUT.TXT
1
3 2 1 2 2 3 2 1 3
2 1 2 1 3
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!