Небезпечні друзі
Limits: 3 sec., 256 MiB
Ваше місто закрили на карантин — відтепер з нього не можна ані виїхати, ані в’їхати до нього. На момент уведення карантину в місті проживало n людей, причому деякі пари з них є друзями та контактують щодня між собою. Оскільки всі мешканці вашого міста є дуже відповідальними громадянами, у перший же ж день карантину всі вони пройшли відповідне тестування та публічно оголосили його результати. Отже, вам відомо, хто з мешканців міста є хворим першого дня після впровадження карантину. Однак хвороба поширюється дуже швидко, а тому є високий ризик заразитися при контакті з уже хворою людиною.
Незважаючи на те, що ви точно не є хворими, ви як відповідальна людина серйозно перейнялися та вирішили вбезпечити себе. Для цього ви обірвете спілкування з деякими зі своїх друзів так, аби недопустити можливості зараження. Наразі вам потрібно вирішити, з ким саме відсьогодні ви перестанете контактувати.
Тому допоможіть собі — напишіть для цього програму!
Input
У першому рядку задано три цілих числа n, m, k — кількість людей у місті (включно з вами), кількість пар друзів серед цих людей та кількість хворих серед них у початковий момент часу.
У наступних m рядках задано пари цілих чисел ui,vi — люди з відповідними номерами є друзями.
Останній рядок містить k чисел — номери людей, хворих у початковий момент часу.
Зауважте, що ваш порядковий номер завжди рівний 1, і ви точно здорові на початку карантину.
Output
У першому рядку виведіть ціле число — мінімальну кількість друзів, з якими варто перестати спілкуватися.
У другому рядку виведіть номери цих друзів у зростаючому порядку.
Constraints
2≤n,
1≤m,
0≤k≤n−1,
5 тестів: n,m≤100,
5 тестів: n,m≤103,
10 тестів: n,m≤105,
5 тестів: n,m≤5⋅105.
Samples
Input (stdin) | Output (stdout) |
---|---|
6 6 2 1 2 2 3 4 5 4 1 5 1 1 6 3 6 | 2 2 6 |
Input (stdin) | Output (stdout) |
---|---|
5 6 1 1 2 1 3 1 4 2 3 3 4 4 5 5 | 3 2 3 4 |
Notes
У першому прикладі є 6 людей та 6 пар друзів. Крім цього, вам відомо, що люди з номерами 3 й 6 були хворими в перший день карантину. Звісно ж, ви перестанете спілкуватися з людиною номер 6, а також — з 2, адже ця людина може бути зараженою, оскільки спілкується з хворим (номер 3). Зауважте, що ви й надалі можете спілкуватися з людьми 4 й 5, адже вони ніяким чином не можуть захворіти. Також ви не повинні вказувати людину 3 у відповіді, адже й до початку карантину ви не спілкувалися з нею.
У другому прикладі варто перестати спілкуватися з усіма вашими друзями, адже всі вони будуть зараженими після певного часу.