Một k-path trên một đồ thị vô hướng cho trước là một đường đi có chính xác k cạnh và không chứa các đỉnh lặp lại. Cho một đồ thị vô hướng G và một giá trị nguyên k, hãy đếm có bao nhiêu k-path trên G. Có 6 k-path độ dài 3 trên đồ thị trong Hình 2, đó là: 1-2-3-4, 2-3-4-1, 3-4-1-2, 4-1-2-3, 2-1-3-4, 4-1-3-2.

Đầu vào

Đầu vào bao gồm các dòng sau:

• Dòng 1: chứa hai số nguyên n và k (1 ≤ n ≤ 30, 1 ≤ k ≤ 10) trong đó n là số đỉnh của đồ thị G (các đỉnh được đánh số 1, 2, ..., n).
• Dòng 2: chứa một số nguyên m (1 ≤ m ≤ 60) là số cạnh của đồ thị G.
• Dòng i + 2: chứa hai số nguyên u và v đại diện cho hai điểm cuối của cạnh thứ i của G (với i = 1, ..., m).

Đầu ra

Đầu ra chứa số lượng các k-path của đồ thị G.

Input

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

Output

6