eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Ужин

Ужин

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Вот уже несколько лет северная конференция практической комбинаторики (NCPC), собирает всё большее число участников. В этом году команда организаторов ожидает рекордного количества участников. В связи с политикой организации этого престижного мероприятия, на сайте конференции было давно сообщено, что оно будет проходить в Гранд Отеле в Стокгольме. В отеле есть два больших обеденных зала, но, к сожалению, в каждый из этих залов может поместиться только до двух третей участников NCPC, так что участникам придется быть разделёнными на две группы.

Это ограничение требует некоторого творческого мышления организаторов для участия всех команд во время конференции на ужине: они могут разделить участников на две части, каждая из которых не больше 2/3 от всей группы. Во время встречи применяются некоторые остроумные правила разделения на группы, чтобы во время ужина они могли бы рассказать другим участникам о своих увлечениях. В конце концов, пока есть некоторые великие правила логики, согласно которых можно определить, в каком из двух обеденных залов вы будете сидеть, вы (как математик) были бы от этого только счастливы! После некоторого размышления им пришла в голову следующая мысль для разделения участников: выбрать такой минимальный год Y для разделение участников на две части, что каждая пара в первой части встретились впервые до года Y и каждая пара во второй части встретились в первый раз именно в году Y или после года Y? Было решено четко квалифицировать это утверждение как соответствующее правило для всех из них, но возник закономерный вопрос, а будет ли это возможно?

Входные данные

Первая строка содержит количество участников N (4N400) и число c известных первых встреч. Каждая из следующих c строк имеет формат a b y: участники a и b (1 a < b n) встретились в первый раз в год y (1948 y < 2008). Ни одна пара участников не встречается в списке более чем один раз, и также нет в списке пар, которые, как предполагается, впервые встречаются только сейчас (текущий год 2008).

Выходные данные

Для каждого теста выведите либо наименьший год Y такой, что можно разделить участников на две части, ни одна из которых не содержит более 2n/3 людей, таких, что все люди в первой части первый раз встретились до года Y, а все люди во второй части впервые встретились в год или после Y. Если же такого года нет, выведите "Impossible".

Пример

Входные данные #1
4 6
1 2 1987
2 3 1987
1 3 1987
2 4 1987
1 4 1987
3 4 1987
Выходные данные #1
Impossible
Источник 2008 Nordic Collegiate Programming Contest, October 4, Problem D