Cho đồ thị gồm ~ n ~ đỉnh đánh số từ 1 đến ~ n ~, đỉnh thứ ~ i ~ có màu ~ c_i ~. Người ta thêm lần lượt ~ m ~ cạnh vô hướng vào đồ thị, cạnh thứ ~ j ~ nối hai đỉnh ~ u_j, v_j ~.

Yêu cầu: Sau mỗi bước thêm cạnh, đếm số cặp đỉnh ~ (i, j) ~ cùng màu mà từ ~ i ~ có thể đến ~ j ~ qua các cạnh của đồ thị ~ (i < j) ~.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương ~ n, m ~ ~ ( n ≤ 10^5, m ≤ 2.10^5) ~;
• Dòng thứ hai chứa ~ n ~ số nguyên dương ~ c_1, c_2, …, c_n ~ ~ ( c_i ≤ 10^9 ) ~;
• ~ m ~ dòng tiếp, dòng thứ ~ j ~ chứa hai số nguyên dương ~ u_j, v_j ~.

Kết quả

Gồm ~ m ~ dòng, mỗi dòng là số cặp ~ (i,j) ~ cùng màu mà từ ~ i ~ có thể đến được ~ j ~ qua cách cạnh của đồ thị.

Ví dụ:

Input 1

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

Output 1

0
0
2
2