Bánh được một phần thưởng vì kết quả học tập tốt đó là được đi du lịch ở thành phố Barcelona. Một thành phố được quy hoạch và xây dựng dạng bàn cờ rất đẹp. Sau khi nhận phòng và ăn uống xong, Bánh làm một khảo sát nhỏ là đi dạo bộ trên đường phố với quy tắc khi nào gặp ngã tư hoặc ngã ba thì rẽ phải gần nhất. Sau một hồi đi dạo thì quay về lại được khách sạn. Liên tưởng đến bài học lý thuyết đồ thị ở trường, Bánh nhờ anh chị giải giúp bài toán sau:

Cho một đơn đồ thị vô hướng ~G = (V, E)~ với ~|V| = n~ là tập đỉnh, ~|E| = m~ là tập cạnh. Hãy lập trình đếm xem trong ~G~ có bao nhiêu chu trình có độ dài nhỏ nhất.

Xét đồ thị như hình vẽ sau:

Các chu trình sau là giống nhau:~(1, 2, 3, 1), (2, 3, 1, 2), (3, 1, 2, 3), (3, 2, 1, 3), (2, 1, 3, 2), (1, 3, 2, 1)~.

Input

Dòng thứ nhất chứa hai số nguyên dương ~n, m~ là số đỉnh và cạnh của đồ thị. Dữ liệu thỏa ~ 3 \le n \le 3.10^3; 3 \le m \le 6.10^3~.

~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u_i, v_i~ là cạnh nối giữa hai đỉnh ~u_i, v_i~ của đồ thị thỏa ~1 \le u_i \neq v_i \le n~.

Output

In ra kết quả cần tìm. Dữ liệu bài toán luôn đảm bảo có ít nhất một chu trình.

Samples

Sample Input 1

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

Sample Output 1

2

Sample Input 2

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

Sample Output 2

2