Сейчас новый год, поэтому Баш хочет подарить подарки своим друзьям. В Гималаях n городов, и m двусторонних дорог между ними. Баш живет в городе s. У Баша ровно один друг в каждом из остальных городов. Так как Баш хочет сделать сюрприз своим друзьям, он решил отправить Пикачу к каждому из своих друзей. Так как не все города достижимы из города, где живет Баш, он посылает Пикачу только тем друзьям, которые живут в достижимых городах. Также, он хочет послать их как можно раньше.

Баш нашел, какое минимальное время необходимо каждому из Пикачу, чтобы добраться до места назначения. Так как он перфекционист, он уведомил всех своих друзей о времени прибытия подарка. Все Пикачу двигаются со скоростью 1 метр в секунду. Друзья Баша будут расстроены, если подарки задержаться. К сожалению, команда Р на свободе и знает о плане Баша. Они хотят максимизировать число друзей Баша, которые расстроятся.

Они планируют разрушить ровно один из n - 1 городов, в которых живут друзья. Друг, которых жил в этом городе, умирает, поэтому он тоже расстраивается.

Заметьте, что если город разрушен, то все дороги, ведущие в этот город, также разрушены, поэтому некоторым Пикачу может потребоваться выбрать другой, более длинный путь.

Также заметьте, что только те друзья, которые ждут подарка, могут считаться расстроенными, даже если они умирают.

Так как Баш — уже легенда, помогите в этот раз команде Р и найдите максимальное возможное число друзей, которые будут расстроены, если разрушен ровно один город.