Эмия Кирицугу потерял своего верного слугу в тяжёлой схватке и сейчас пытается укрыться в семейном поместье Айнцберн. В нём $n$ комнат, которые соединены $m$ коридорами.

Великий царь Гильгамеш преследует Эмию и уже добрался до его поместья. За один час Гильгамеш \textbf{одновременно} уничтожает \textbf{все} комнаты из которых выходит \textbf{наибольшее} количество коридоров. Вместе в комнатой уничтожаются \textbf{все} коридоры, которыми она была связана с какими-то другими комнатами.

Эмия Кирицугу очень устал, поэтому хочет перевести силы перед битвой с Гильгамешем. Другими словами, он хочет прятаться как можно дольше, поэтому заранее выберет одну из комнат, которую Гильгамеш уничтожит последней.

Помогите Кирицугу определить, какое максимальное количество часов он сможет прятаться от Гильгамеша.
