Как известно, в столице Берляндии есть n перекрёстков. На некоторых их этих перекрёстков находятся жилые дома. Пусть a_i — это количество человек в семье, проживающей в доме, который находится на перекрёстке i для всех 1 ≤ i ≤ n. Если a_i равно нулю, будем считать, что на этом i-м перекрёстке нет жилого дома.

Некоторые перекрёстки соединены дорогами. Всего в Берляндии m дорог. По каждой дороге можно ходить в любом направлении. Каждая дорога соединяет два различных перекрёстка. Любые два перекрёстка соединены не более чем одной дорогой. От любого перекрёстка можно добраться по дорогам города до любого другого перекрёстка. Назовём расстоянием между перекрёстками i и j минимальное количество дорог, по которым нужно пройти, чтобы добраться от перекрёстка i до перекрёстка j.

Когда одна семья ходит в гости к другой семье, каждый человек находит себе ровно одного собеседника из другой семьи, и они вдвоем разговаривают между собой. Двум семьям общаться скучно, если какой-то человек останется без собеседника.

По какой-то непонятной причине правительство Берляндии попросило вас найти два ближайших жилых дома v и u, таких что если семья из дома v придёт в гости к семье из дома u, то им будет скучно общаться, то есть a_v > 0, a_u > 0, a_v ≠ a_u и расстояние от v до u минимально. Гарантируется, что существуют два жилых дома с различным количеством жильцов.