زيادة الأبقار سببت ازدحام طرق الحظيرة. يدرس Farmer John الاختناقات لتخفيف «الزحام» وقت الحلب.

$M$ ($1 \le M \le 50,000$) طرق أحادية تصل نقطتين مختلفتين من $N$ ($1 \le N \le 5,000$) تقاطعات $1..N$، الحظيرة في $N$. كل طريق لرقم أكبر، فلا دورات وكلها للحظيرة. قد تتعدد الطرق بين زوج نقاط.

وقت الذروة تنطلق الأبقار من مراعيها للحظيرة: هي بالضبط التقاطعات بلا طريق وارد. «المسار» سلسلة طرق من المرعى للحظيرة.

أوجد أكبر عدد مسارات ممكنة تحتوي طريقًا واحدًا معينًا لتحديد الأشد ازدحامًا. الجواب يتسع لصحيح موقّع 32 بت.

الإدخال

السطر 1: الصحيحان $N$ و$M$ بمسافة.

الأسطر $2..M+1$: تقاطعان بمسافة.

الإخراج

السطر 1: أكبر عدد مسارات تمر بطريق واحد.

أمثلة

الإدخال 1

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

الإخراج 1

4

ملاحظة

أربعة مسارات ممكنة للحظيرة:

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

المصدر: USACO مارس 2007.