#1199. COLORPATH - Màu đường đi

Một đồ thị đỉnh, đỉnh thứ i được tô màu . Có cạnh hai chiều, cạnh thứ kết nối hai chiều trực tiếp giữa hai đỉnh và . Đường đi là một danh sách các đỉnh thỏa mãn tồn tại đường nối trực tiếp giữa và và các đỉnh khác nhau đôi một.

Yêu cầu: Hãy xác định số đường đi khác nhau thỏa mãn không có hai đỉnh nào trên đường đi cùng màu. Hai đường đi và được coi là khác nhau nếu như tồn tại ít nhất một vị trí sao cho .

Dữ liệu vào:

• Dòng đầu tiên chứ ba số nguyên dương ;
• dòng tiếp theo, dòng thứ chứa hai số nguyên dương xác định cạnh thứ của đồ thị. Dữ liệu đảm bảo không có cạnh nào được lặp lại hai lần.

Dữ liệu ra:

• Ghi ra một số nguyên duy nhất là số lượng đường đi thỏa mãn.

Ví dụ:

Dữ liệu vào:

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

Dữ liệu ra:

10

Giải thích:

Ta có các đường đi sau:

Giới hạn:

• số test có ;
• số test có ;
• số test có ;
• số test có .