Problem description

Mechanika kwantowa była działem nauki, który od zawsze fascynował Jasia. Teraz, gdy ma już za sobą maturę, ma więcej czasu na eksperymenty, więc postanowił zbudować układ, w którym mógłby badać stan cząstek splątanych. Układ składa się z N komór, w których każda zawiera dokładnie jedną cząstkę. Komory połączone są ze sobą dokładnie N − 1 tunelami kwantowymi, w taki sposób że każda para cząsteczek może się skomunikować za pomocą (być może niebezpośredniego) połączenia tunelami na dokładnie jeden sposób.

Jasio poczynił już pewne obserwacje, ale teraz chciałby je potwierdzić doświadczalnie. Będzie do tego jednak najpierw potrzebował zneutralizować układ. Niektóre cząstki w układzie komór Jasia są aktywne, a niektóre nie. Jego zadaniem jest wprowadzić wszystkie cząstki w stan nieaktywny, tak by mógł kontynuować eksperymenty w warunkach sterylnych.

Do neutralizacji skorzysta z pewnej własności kwantowej – niektóre cząstki podlegają splątaniu. Na potrzeby tego zadania możemy przyjąć, że cząstki w danych dwóch komorach a i b mogą ulec splątaniu, jeżeli odległość między nimi (mierzona w liczbie tuneli na ścieżce między nimi) jest nie większa niż K. Jeżeli jakieś dwie cząstki są ze sobą splątane, to Jasio może skorzystać z takiej więzi i dokonać zamiany stanów tych cząstek. Każda z dwóch cząstek jeżeli była aktywna, to po takiej operacji będzie nieaktywna, oraz na odwrót – jeżeli była nieaktywna, to się uaktywni.

Napisz dla Jasia program, który sprawdzi, czy możliwa jest neutralizacja układu, a jeżeli tak, to jaka jest najmniejsza liczba operacji zamian, by osiągnąć zamierzony efekt.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N i K oznaczające odpowiednio liczbę komór w układzie kwantowym Jasia, oraz maksymalną odległość między splątanymi cząstkami.

W drugim wierszu wejścia znajduje się N liczb całkowitych. i-ta z nich oznacza stan cząstki w i-tej komorze na początku eksperymentu, gdzie 1 oznacza cząstkę aktywną, a 0 cząstkę nieaktywną.

W i-tym z kolejnych N − 1 wierszy znajdują się dwie liczby naturalne a_i oraz b_i oznaczające bezpośredni tunel między komorami o tych numerach.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita oznaczająca minimalną liczbę operacji koniecznych do zamiany stanu wszystkich cząsteczek na nieaktywne, albo napis NIE jeżeli nie jest to możliwe.

Ograniczenia

2 ≤ N ≤ 200 000, 1 ≤ K ≤ N.

Przykład

7 2
1 0 0 1 0 1 1
1 2
2 3
3 4
5 2
6 5
7 3

3

4 2
1 1 0 1
1 2
1 3
1 4

NIE