Gộp Tháp

Bạn có $n$ chiếc đĩa, đĩa thứ $i$ có bán kính $i$. Ban đầu các đĩa này được chia vào $m$ tháp: mỗi tháp chứa ít nhất một đĩa, và các đĩa trong mỗi tháp được xếp theo thứ tự bán kính giảm dần từ dưới lên trên.

Bạn muốn gộp tất cả các đĩa lại thành một tháp duy nhất. Để làm điều đó, bạn có thể chọn hai tháp khác nhau $i$ và $j$ (mỗi tháp chứa ít nhất một đĩa), lấy một số (có thể là tất cả) đĩa trên cùng của tháp $i$ và đặt lên trên tháp $j$ theo đúng thứ tự, với điều kiện đĩa trên cùng của tháp $j$ phải lớn hơn tất cả các đĩa được di chuyển. Bạn có thể thực hiện thao tác này bao nhiêu lần tùy ý.

Gọi độ khó của một tập các tháp là số thao tác tối thiểu cần thực hiện để gộp tất cả các đĩa lại thành một tháp duy nhất.

Bạn được cho $m-1$ truy vấn. Mỗi truy vấn gồm hai số $a_i$ và $b_i$, nghĩa là "gộp tháp $a_i$ và tháp $b_i$" (lấy tất cả đĩa của hai tháp này và tạo thành một tháp mới chứa tất cả chúng, xếp theo thứ tự bán kính giảm dần từ trên xuống dưới). Tháp kết quả nhận chỉ số $a_i$.

Với mỗi $k\in [0,m-1]$, hãy tính độ khó của tập các tháp sau khi thực hiện $k$ truy vấn đầu tiên.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số đĩa và số tháp.
• Dòng thứ hai chứa $n$ số nguyên $t_1,t_2,\dots ,t_n$, trong đó $t_i$ là chỉ số tháp mà đĩa $i$ thuộc về. Mỗi giá trị từ $1$ đến $m$ xuất hiện ít nhất một lần.
• $m-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$ và $b_i$ mô tả một truy vấn. Các giá trị $a_i,b_i$ được chọn sao cho hai tháp này tồn tại trước truy vấn thứ $i$.

Dữ liệu ra

In ra $m$ số nguyên. Số thứ $k$ (đánh chỉ số từ $0$) là độ khó của tập các tháp sau khi thực hiện $k$ truy vấn đầu tiên.

Ràng buộc

• $2\le m\le n\le 2·{10}^5$
• $1\le t_i\le m$, mỗi giá trị từ $1$ đến $m$ xuất hiện ít nhất một lần.
• $1\le a_i,b_i\le m$, $a_i\ne b_i$.

Ví dụ