Сегодня отовсюду трубят про выборы. Скандалы, интриги, расследования, разоблачения. В нашем городке Бездорожинске тоже настало время выбирать мэра. Но, чтобы избежать традиционных распрей, мы решили изменить концепцию: победителя определит не слово, а дело. И дело это очень важное — постройка дорог.

В Бездорожинске есть несколько микрорайонов, в которых построено N домов, соединенных M двунаправленными дорогами. Дорог, как водится, не хватает. Дороги между домами не дублируются, и нет дорог, петляющих и приводящих в тот же дом. В микрорайоне(который, к слову, может состоять из одного дома) между любой парой домов существует как минимум один путь по дорогам. А вот из микрорайона в микрорайон дорог нет, и бедным жителям приходится добираться по грязи.

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

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

После того, как вы узнаете текущую схему дорог в Бездорожинске, вам потребуется вывести одно из чисел: "1" или "2" — первым или вторым вы хотите начать предвыборную гонку, соответственно.

Теперь, если сейчас ваша очередь, то вам необходимо вывести два целых числа U V — номера домов, между которыми вы беретесь строить дорогу. Если сейчас ход вашего соперника, то вы получаете два целых числа U V — номера домов, которые соединил ваш оппонент.

Вы должны корректно заканчивать предвыборную гонку, когда в городе останется только один микрорайон или когда оппонент выводит два нуля "0 0".

После вывода не забывайте, пожалуйста, выводить символ новой строки и делать flush-операцию (сброс буфера). Например, fflush(stdout) в C++, System.out.flush() в Java, и flush(output) в Pascal.