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 \leq 10^{5},m \leq {2.10}^{5});\)

+ Dòng thứ hai chứa \(n\) số nguyên dương \(c_{1},c_{2},\ldots,c_{n}\ \left( c_{i} \leq 10^{9} \right);\)

+ \(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ụ: