Эта задача с открытым тестированием. Решения по этой задаче тестируются «в открытую», во время олимпиады. Вы можете не дожидаться окончания олимпиады, чтобы узнать итоговый балл вашего решения по этой задаче.
Как известно, Тимур — лучший поставщик продуктов во всей Московской области. В Московской области существует всего $$$n$$$ ресторанов, в $$$c$$$ из которых Тимур уже поставляет продукты. Также, $$$m$$$ пар ресторанов являются соседями друг для друга, при этом ресторан не может быть соседом сам себе и никакие два ресторана не могут быть соседями дважды.
Так как Тимур не разбирается в рекламе, то новости о его качественной работе распространяются только с помощью сарафанного радио, а именно — ресторан решает нанять Тимура как поставщика, если хотя бы в $$$k$$$ соседей этого ресторана Тимур уже поставляет продукты.
Тимур очень дальновидный, поэтому его интересует, какие из ресторанов однажды наймут его как поставщика. Но так как сейчас он занят развозом товара, он поручил эту непростую задачу Вам!
Первая строка содержит три целых числа $$$n, m, k$$$ $$$(1 \leq k \leq n \leq 2 \cdot 10^5, 1 \leq m \leq min(\frac{n \cdot (n - 1)}{2}, 2 \cdot 10^5))$$$, обозначающие количество ресторанов, количество пар соседей и количество соседей, необходимое для того, чтобы ресторан нанял Тимура, соответственно.
В следующих $$$m$$$ строчках содержится описание пар соседних ресторанов. Каждая строка содержит два различных целых числа $$$u_i, v_i$$$ — номера двух ресторанов, соседних друг другу $$$(1 \leq u_i, v_i \leq n, u_i \neq v_i)$$$. Гарантируется что одна и та же пара не встречается в этом списке дважды.
В следующей строке содержится целое число $$$c$$$ $$$(0 \leq c \leq n)$$$, обозначающее количество ресторанов, в которые Тимур с самого начала поставляет продукты.
В следующей строке содержится $$$c$$$ различных целых чисел от $$$1$$$ до $$$n$$$ — номера ресторанов, в которые Тимур уже поставляет продукты.
В первой строке выведите целое число $$$a$$$ — количество ресторанов, которые однажды наймут Тимура как поставщика.
Во второй строке выведите $$$a$$$ целых чисел — номера всех ресторанов, в которые Тимур будет поставлять продукты, в любом порядке .
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся при прохождении всех тестов этой группы, а также при прохождении тестов необходимых подгрупп. Баллы за соответствующие группы указаны в таблице.
| Группа | Баллы | Дополнительные ограничения | Необходимые группы | Комментарий | |
| $$$n, m$$$ | $$$k$$$ | ||||
| 0 | 0 | – | – | – | Тест из условия |
| 1 | 10 | $$$1 \leq n, m \leq 500$$$ | $$$k = 1$$$ | – | – |
| 2 | 10 | – | $$$k = 1$$$ | 1 | – |
| 3 | 20 | $$$1 \leq n, m \leq 500$$$ | – | 0, 1 | – |
| 4 | 20 | $$$1 \leq n, m \leq 2000$$$ | – | 0, 1, 3 | – |
| 5 | 40 | – | – | 0, 1, 2, 3, 4 | – |
5 5 21 21 32 33 44 531 2 5
5 1 2 3 4 5
Пояснение к тесту из условия выглядит следующим образом:
 |  |  |
Изначально только в три ресторана с номерами 1, 2 и 5 Тимур поставляет продукты. После этого ресторан с номером 3 также решает нанять Тимура, ведь у него есть двое соседей, в которые Тимур уже поставляет продукты. Далее ресторан под номером 4 тоже решает нанять Тимура, ведь его соседи с номерами 3 и 5 уже работают с Тимуром. Таким образом, все 5 ресторанов будут сотрудничать с Тимуром.
