Заочные олимпиады: 1 тур

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

Туннельная система города М. состоит из \(n\) станций метро. Станции соединены между собой двунаправленными туннелями, которых всего \(n - 1\). Между любыми станциями \(v\) и \(u\) есть ровно один простой путь. Каждая ветка метро, которую хочет создать мэр, является простым путём от станции \(a_i\) до станции \(b_i\). Ветки могут пересекаться, то есть иметь общие станции или туннели. Однако, ещё не решено, в какую из двух сторон будут следовать поезда на каждой из веток. А именно, на пути между станциями \(a_i\) и \(b_i\) поезда будут следовать либо от станции \(a_i\) к станции \(b_i\), либо от станции \(b_i\) к станции \(a_i\), но только в одну из сторон.

В городе \(M\) действует особая система тарифов. Каждой станции присваивается целое положительное число \(c_i\) — тарифная зона станции, а стоимость переезда от станции \(v\) до станции \(u\) определяется как \(c_u - c_v\) бурлей. Разумеется, такой переезд разрешен, только если есть ветка метро, по которой поезда идут из \(v\) в \(u\). Мэр города не хочет, чтобы между какими-то двумя станциями на одной ветке стоимость проезда была отрицательной, поэтому было принято решение выбрать направления движения поездов по веткам и изменить тарифные зоны всех станций города таким образом, чтобы на каждой ветке тарифные зоны станций строго возрастали, если рассмотреть её в сторону движения поездов.

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

Обратите внимание, что в некоторых группах тестов минимизировать ответ не нужно, а требуется лишь определить, возможно ли назначить тарифные зоны нужным образом.