Програмчлалын олимпиадын бодлогын архив

N ширхэг процесс (програм) байгаа ба тэдгээрийг ажиллуулж дуусгах ёстой. Хэрэв Процесс 1-ийг ажиллаж дууссаны дараа л Процесс 2 ажиллаж эхэлж чадах бол Процесс 2-ыг Процесс 1-ээс хамаарч байна гэж үзнэ. Хугацаа хэмнэхийн үүднээс хамааралгүй хоёр процессыг зэрэг хоёр процессор дээр ажиллуулж болно. Процессуудын хоорондох хамаарал өгөгдсөн бол төгсгөлгүй олон процессортой компьютер дээр эдгээр процессуудыг ажиллуулж дуусах хамгийн богино хугацааг ол. Мөн энэ олсон богино хугацаандаа процессуудыг ажиллуулах үед хамгийн багадаа хэдэн процессор хэрэгтэйг ол. Процесс бүр нэг нэгж хугацаанд биелэгдэж дуусдаг. Процессуудыг 1-ээс N хүртлэх натурал тоонуудаар дугаарласан (N<=200).

Input

Оролтын эхний мөрөнд процессуудын нийт тоо N болон тэдгээрийн хоорондын хамаарлын тоо M гэсэн хоёр бүхэл тоо зайгаар тусгаарлагдан өгөгдөнө. Дараагийн M ширхэг мөрөнд процессуудын хоорондын хамаарлыг тодорхойлно. Жишээ нь нэг мөрөнд "2 3" гэж бичигдсэн байвал Процесс 3-ыг ажиллуулж эхлүүлэхийн тулд Процесс 2 ажиллаж дууссан байх ёстой гэсэн үг. Өгөгдөл зөв байх ба дор хаяж нэг шийдтэй байна.

Output

Гаралт дээр зайгаар тусгаарлагдсан хоёр бүхэл тоог гаргана. Эхний тоо T нь бидэнд төгсгөлгүй олон процессортой компьютер байсан үед процессуудыг ажиллуулж дуусгахад шаардлагатай хамгийн богино хугацааны нэгжийн тоог илэрхийлнэ. Хоёр дахь тоо нь процессуудыг Т хугацаанд ажиллуулж дуусгахын тулд хамгийн багадаа хэдэн процессор хэрэгтэйг заана.

Example

Input:
6 6
1 4
2 5
3 6
4 6
4 5
5 6


Output:
4 2