Карта скарбів
Limits: 2 sec., 256 MiB
Зеник та Марічка знайшли картку скарбів Львова.
Львів можна представити у вигляді неорієнтовного зв’язного графа, вершини якого представляють перехрестя, а ребра — дороги між ними.
Згідно з легендою, скарб заховано в одному із перехресть. Творці карти спочатку для кожного перехрестя знайшли і позначили найкоротшу відстань (кількість доріг) від нього до скарбу. Після цього, для кожного значення відстані було стерто позначення із рівно одного перехрестя з такою відстанню. Тобто для кожного значення \(d\), якщо існує \(k\) перехресть на відстані \(d\), для рівно \(k-1\) з них буде записано значення \(d\), а для останнього значення стерто.
Ваше завдання — за заданою картою знайти усі перехрестя, в яких може бути скарб.
Input
У першому рядку задано два цілих числа \(n\) та \(m\) — кількість перехресть та доріг відповідно.
У наступних \(m\) рядках задано пари чисел \(u_i\) та \(v_i\) — номери перехресть, з’єднаних відповідною дорогою. Гарантовано, що заданий граф зв’язний, та не містить петель та кратних ребер.
У наступному рядку задано \(n\) цілих чисел \(h_i\) через пробіл. Число -1 позначає, що відстань до відповідного перехрестя не була позначена, тоді як будь-яке інше число позначає відстань від скарбу до відповідного перехрестя.
Гарантовано, що карта коректна та її побудова відповідає опису в умові.
Output
У першому рядку виведіть одне ціле число \(c\) — кількість вершин, в яких міг міститись скарб.
У наступному рядку виведіть \(c\) чисел через пробіл у порядку зростання — номери перехресть, які можуть містити скарб.
Constraints
\(2 \le n \le 2 \cdot 10^5\),
\(1 \le m \le 2 \cdot 10^5\),
\(-1 \le h_i < n\).
Samples
Input (stdin) | Output (stdout) |
---|---|
3 2 2 1 1 3 -1 -1 -1 | 2 2 3 |
Input (stdin) | Output (stdout) |
---|---|
7 10 1 4 2 3 3 5 7 5 3 4 6 3 2 6 7 2 2 5 1 3 1 -1 -1 -1 2 2 -1 | 1 4 |
Notes
У першому прикладі відстань до усіх перехресть є невідомою. Неважко переконатись, що лише перехрестя 2 та 3 відповідають побудові карти, описаній в умові.
У другому прикладі задано граф, зображений на рисунку нижче.
Лише перехрестя з номером 4 могло містити скарб.
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|