Степан нарешті дочекався щорічної відпустки. Країну, куди він вирішив помандрувати, можна представити у вигляді ~n~ міст і ~m~ двонаправлених доріг, що їх зʼєднують. Кожна дорога має однакову довжину, і можна дістатися будь-якого міста з будь-якого іншого, подорожуючи цими дорогами. Шлях від міста ~a~ до міста ~b~ визначається як послідовність доріг, що, починаючи з міста ~a~ і послідовно проходячи дороги в цій послідовності, потрапляє в місто ~b~. Довжина шляху визначається як кількість доріг на цьому шляху.

Степан зазвичай бронював найдорожчий готель в одному з міст, а потім починав планувати свою подорож. Щоб полегшити планування, він записав довжину найкоротшого шляху від готелю до кожного міста.

У захваті від довгоочікуваної відпустки Степан зовсім забув, у якому місті знаходиться готель. Він точно не хоче пропускати поїздку, тому просить вас визначити, в яких містах може бути розташований готель.

Формат вхідних даних

У першому рядку — натуральні числа ~n~ і ~m~ — кількість міст і кількість доріг, що їх зʼєднують (~1 ≤ n ≤ 5 · 10^4~, ~n-1 ≤ m ≤ 10^5~).

В ~i~-му з наступних ~m~ рядків є числа ~u_i~ та ~v_i~ - є дорога між містами ~u_i~ та ~v_i~ (~1 ≤ u_i, v_i ≤ n~, ~u_i \neq v_i~). Між будь-якими двома містами існує щонайбільше одна дорога.

В останньому рядку ~n~ цілих чисел - ~i~-те число ~d_i~ вказує на відстань від ~i~-го міста до міста, де розташований готель, або -1, якщо Степан не записав цю відстань (~-1 ≤ d_i < n~).

Формат вихідних даних

У першому рядку напишіть кількість міст, де може бути розташований готель.

У другому рядку запишіть у порядку зростання міста, де може розташовуватися готель.

Оцінювання

• 10 балів ~m+1=n≤5000~,~u_i+1=v_i~
• 20 балів ~d_i =-1~ для ~i>1~
• 30 балів ~n,m≤5000~
• 40 балів Без додаткових обмежень.

Пояснення до першого прикладу:

Шлях із міста 4 до міста 1 має довжину 2, тоді як шлях із міста 4 до міста 7 має довжину 3. Таким чином, місто 4 задовольняє обом умовам, і готель може бути розташований там. Те саме стосується міста, позначеного цифрою 6.

Приклад вхідних даних

7 6
1 2
1 3
3 4
3 5
3 6
5 7
2 -1 -1 -1 -1 -1 3

Приклад вихідних даних

2
4 6

Приклад вхідних даних

6 6
1 2
2 3
3 4
4 5
5 6
6 1
2 -1 -1 1 -1 -1

Приклад вихідних даних

2
3 5

Приклад вхідних даних

4 3
1 2
2 3
3 4
1 -1 -1 1

Приклад вихідних даних

0