Đồ thị là một cấu trúc toán học gồm một tập các đỉnh và một tập các cạnh, mỗi cạnh nối hai đỉnh. Một đồ thị có \(4\) đỉnh và \(3\) cạnh được minh họa trong phần giải thích ví dụ bên dưới.

Một đường đi trong đồ thị là một danh sách có thứ tự gồm ít nhất hai đỉnh, sao cho giữa hai đỉnh liên tiếp trong danh sách luôn có một cạnh. Trong bài này, ta chỉ xét các đường đi đơn, nghĩa là không có đỉnh nào xuất hiện nhiều hơn một lần. Danh sách có thứ tự, nên chẳng hạn 5-6-7, 5-7-6 và 7-6-5 được coi là những đường đi khác nhau.

Mỗi đỉnh của đồ thị có một trong \(K\) màu. Hãy tìm số đường đi đơn mà không có hai đỉnh nào cùng màu.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(K\), lần lượt là số đỉnh, số cạnh và số màu.

Dòng thứ hai chứa \(N\) số nguyên từ \(1\) đến \(K\), là màu của các đỉnh theo thứ tự từ đỉnh \(1\) đến đỉnh \(N\).

Mỗi dòng trong \(M\) dòng tiếp theo mô tả một cạnh bằng hai số nguyên \(a\) và \(b\), là hai đỉnh mà cạnh đó nối. Giữa hai đỉnh bất kỳ có nhiều nhất một cạnh.

Dữ liệu ra

In ra một số nguyên là số đường đi có các đỉnh mang màu đôi một khác nhau. Kết quả luôn nhỏ hơn \(10^{18}\).

Ràng buộc

• \(1 \le N,M \le 300\,000\) và \(1 \le K \le 5\), với giới hạn cụ thể theo từng nhóm bên dưới.
• Màu của mỗi đỉnh là một số nguyên từ \(1\) đến \(K\).
• Với mỗi cạnh, \(1 \le a,b \le N\) và \(a \ne b\).
• Giữa hai đỉnh bất kỳ có nhiều nhất một cạnh; các cạnh là vô hướng.
• Mỗi đường đi được tính phải có ít nhất hai đỉnh và các đỉnh mang màu đôi một khác nhau.
• Kết quả nhỏ hơn \(10^{18}\).

Phân nhóm

• Mỗi nhóm kiểm thử gồm một số bộ dữ liệu. Bạn chỉ nhận được điểm của một nhóm khi giải đúng tất cả các bộ dữ liệu trong nhóm đó.

• Điểm của một lần nộp là tổng điểm các nhóm đạt được. Điểm cuối cùng là điểm cao nhất của một lần nộp.

• Nhóm 1 (23 điểm): \(1 \le N,M \le 100\), \(1 \le K \le 4\).

• Nhóm 2 (20 điểm): \(1 \le N,M \le 300\,000\), \(1 \le K \le 3\).
• Nhóm 3 (27 điểm): \(1 \le N,M \le 300\,000\), \(1 \le K \le 4\).
• Nhóm 4 (30 điểm): \(1 \le N,M \le 100\,000\), \(1 \le K \le 5\).

Ví dụ

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

10

9 11 4
1 2 3 4 1 2 1 2 2
1 2
1 3
2 3
2 4
3 6
6 2
6 5
4 3
4 5
7 8
9 8

70

Nguồn

Baltic Olympiad in Informatics 2018, ngày thi thứ hai.