Bò tăng nhanh làm tắc đường tới chuồng. Farmer John nghiên cứu nút thắt giảm «kẹt xe» lúc vắt sữa.

$M$ ($1 \le M \le 50,000$) đường một chiều nối hai điểm khác của $N$ ($1 \le N \le 5,000$) giao điểm $1..N$, chuồng ở $N$. Tới số lớn hơn nên không chu trình, tất cả tới chuồng. Nhiều đường cùng cặp có thể.

Giờ cao điểm bò từ nơi ăn cỏ đến chuồng: chính xác điểm không đường vào. «Lộ trình» là chuỗi đường từ đó đến chuồng.

Tìm số lộ trình có thể chứa một đường cho trước lớn nhất để biết đường bận nhất. Đáp án vừa nguyên có dấu 32 bit.

Dữ liệu vào

Dòng 1: nguyên $N$, $M$ cách dấu cách.

Dòng $2..M+1$: hai giao điểm cách dấu cách.

Dữ liệu ra

Dòng 1: số lộ trình qua một đường lớn nhất.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

4

Ghi chú

Bốn lộ trình có thể tới chuồng:

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

Nguồn: USACO tháng 3 năm 2007.