Cho đồ thị vô hướng gồm \(n\) đỉnh và \(m\) cạnh. Hãy đếm số cách tô màu \(n\) đỉnh bằng \(k\) màu sao cho không có hai đỉnh kề nhau nào cùng màu.

Đây là bài toán Graph Coloring kinh điển. Dùng quay lui để thử tất cả cách tô màu.

Input

Dòng đầu chứa 3 số \(n\), \(m\), \(k\) (\(1 \le n \le 10\), \(0 \le m \le 45\), \(1 \le k \le 4\)).
\(m\) dòng sau, mỗi dòng chứa 2 số \(u, v\) (\(1 \le u < v \le n\)) — một cạnh của đồ thị.

Output

In ra số cách tô màu thỏa mãn.

Example

4 3 3
1 2
2 3
3 4

Output:

24