Јован је одлучио да окити стабло које му расте у дворишту за нову годину. Јованово стабло има \(N\) чворова и \(N-1\) грану, тако да се од сваког чвора може доћи до сваког другог на јединствен начин коришћењем неког скупа грана. Од тих \(N\) чворова, чвор нумерисан бројем \(1\) је посебан, и њега називамо корен стабла. Подстабло чвора \(u\) је скуп свих чворова \(v\), таквих да \(u\) припада скупу чворова који су на путу између чвора \(v\) и корена стабла. Специјално, чвор \(u\) припада подстаблу чвора \(u\).

На чвору \(i\) виси украс боје \(b_i\). Разнобојност стабла дефинишемо као број различитих компоненти исте боје. Два чвора припадају истој компоненти уколико је могуће доћи од једног до другог тако да сви чворови на том путу имају исту боју (укључујући и почетни и крајњи).

Јован још увек није сигуран како да окити стабло. Он ће на стаблу извршити \(Q\) промена облика:

\(u\) \(c\) - Јован ће заменити све украсе на чворовима који припадају подстаблу чвора \(u\) са украсима боје \(c\).

Помозите Јовану да окити стабло и испишите разнобојност стабла после сваке измене.

Опис улаза

У првом реду налазе се бројеви \(N\) и \(Q\). У наредних \(N-1\) линија, налазе се по два броја \(u\) и \(v\), који представљају гране стабла. У наредној линији, налази се \(N\) бројева, од којих је \(i\)-ти број \(b_i\) - боја украса који виси на чвору \(i\). У последњих \(Q\) линија налазе се по два броја \(u\) и \(c\), који представљају измене на стаблу.

Опис излаза

За сваку од \(Q\) измена исписати разнобојност стабла после те измене.

Ограничења

• \(1 \leq N, Q \leq 2 \cdot 10^{5}\).
• \(1 \leq b_i, u, c \leq N\).

Тест примери су подељени у пет дисјунктних група:

• У тест примерима вредним 5 поена: \(N, Q \leq 10^3\).
• У тест примерима вредним 15 поена: \(c = 1\), тј. свака измена има исту боју.
• У тест примерима вредним 15 поена: Постоји грана између \(i\) и \(i-1\) за свако \(2 \leq i \leq N\).
• У тест примерима вредним 20 поена: Постоји грана између \(i\) и \(\lfloor \frac{i}{2} \rfloor\) за свако \(2 \leq i \leq N\).
• У тест примерима вредним 45 поена: Нема додатних ограничења.

Примери

Пример 1

Улаз

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

Излаз

5
4
1
2

Објашњење

Након прве измене, истобојне компоненте се састоје од чворова: \(\{1,3\},\{2\},\{4\},\{5\},\{6\}\).
Након друге измене, истобојне компоненте се састоје од чворова: \(\{1,3\},\{2,4\},\{5\},\{6\}\).
Након треће измене, истобојне компоненте се састоје од чворова: \(\{1,2,3,4,5,6\}\).
Након четврте измене, истобојне компоненте се састоје од чворова: \(\{1,3,6\},\{2,4,5\}\).