Giáng sinh này, Minato đã mua một cây thông Noel siêu to khổng lồ đặt trong nhà mình. Cây thông Noel mà Minato mua có dạng một đồ thị ~n~ đỉnh và ~n - 1~ cạnh sao cho hai đỉnh bất kì đều có thể đến được nhau thông qua một số cạnh.

Mỗi đỉnh của cây thông có một cái vớ màu trắng hoặc màu đỏ. Cháu nội của Minato là Boruto lại rất thích được tặng quà giáng sinh, hơn nữa màu đỏ lại là màu yêu thích của cậu ấy.

Boruto muốn mọi người chú ý đến những chiếc vớ màu đỏ nhiều hơn, để mọi người đặt thật nhiều quà vào những chiếc vớ này. Vì vậy cậu ấy muốn với mỗi cặp vớ màu đỏ bất kì, tất cả các cạnh nằm giữa hai đỉnh chứa cặp vớ này đều phải được gắn đèn LED.

Biết được ước muốn của cháu nội mình, Minato đã nhờ Kushina mua rất nhiều sợi đèn LED. Với mỗi sợi dây, Boruto có thể chọn 2 đỉnh ~u~ và ~v~, sau đó sẽ trải sợi đèn LED phủ tất cả các cạnh nằm giữa hai đỉnh này.

Minato đã thực hiện ~q~ lần thay đổi. Mỗi lần thay đổi, Minato sẽ chọn 1 đỉnh ~x (1 \le x \le n)~, nếu đỉnh đó có vớ màu trắng, thì sẽ được thay bởi cái vớ màu đỏ và ngược lại.

Sau mỗi lần thay đổi, Minato yêu cầu Boruto trả lời xem cần ít nhất bao nhiêu sợi dây đèn để có thể thực hiện được ước muốn của mình.

Input

• Dòng đầu tiên chứa số nguyên dương ~n, q~ ~(1 \le n, q \le 5 \times 10^5)~ là số lượng đỉnh của cây thông Noel và số lượng thay đổi mà Minato thực hiện.
• Dòng thứ hai chứa ~n~ số, số thứ ~i~ mô tả màu sắc của chiếc vớ ở đỉnh ~i~. (0 nếu là màu trắng, 1 nếu là màu đỏ)
• ~n - 1~ dòng tiếp theo, mối dòng chứa hai số nguyên dương ~u, v(1 \le u, v \le n )~ mô tả cạnh nối hai đỉnh ~u~ và ~v~.
• Tiếp theo gồm có ~q~ dòng biểu diễn các lần thay đổi, mỗi dòng sẽ có một số là chỉ số của đỉnh được thay loại vớ.

Output

Ghi ra ~q + 1~ dòng. Dòng đầu tiên ghi ra số lượng sợi đèn LED ít nhất để có thể Boruto thực hiện ước muốn của mình khi chưa thực hiện thay đổi nào. Dòng thứ ~i~ trong ~q~ dòng tiếp theo ghi ra số lượng sợi đèn LED ít nhất để có thể Boruto thực hiện ước muốn của mình sau lần thay đổi thứ ~i~.

Giới hạn

• Subtask 1 (10% số điểm):

  • Cây thông Noel có dạng đường thẳng

• Subtask 2 (10% số điểm):

  • Cây thông Nodel có dạng hình chữ T

• Subtask 3 (30% số điểm):

  • ~n, q \le 10^3~

• Subtask 4 (50% số điểm):

  • Không có giới hạn gì thêm

Sample Input

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

Sample Output

1 
1
1
2
2

Note

• Cây có dạng thẳng là cây có các đỉnh có bậc tối đa là 2. (Bậc của một đỉnh là số lượng cạnh nối với đỉnh đó)
• Cây hình chữ T là đồ thị có đúng một đỉnh có bậc bằng 3, và tất cả những đỉnh khác có bậc tối đa là 2.