Тренировка по теме «Графы»

Соревнование завершилось 04.03.17 в 19:40

A. Пора на финал

Автор задачи: Хаустов Павел
Источник: Летние сборы школьников ТПУ 2012
Ограничение по времени: 1 с.
Ограничение по памяти: 64 МБ

Паша, Слава и Кирилл очень хотят попасть на финал ACM ICPC чемпионата мира по программированию в Египет. Правда есть одна проблема...

Финал проходит в середине февраля. В это время в Томске примерно 40 градусов ниже нуля. Добираться до Египта придется, скорее всего, через Москву.

В Москве в это время температура колеблется около нуля. В Египте же финалистов ждет температура порядка 35 градусов выше нуля.

Вот такие перепады температуры ждут Томичей в случае выхода на финал.

И проблема даже не в том, что придется тащить с собой непонятно какую одежду и переодеваться пока горит спичка.

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

Существует N городов. Города пронумерованы натуральными числами от 1 до N. В каждом из них известно значение среднесуточной температуры.

Известно, что между некоторыми парами городов есть авиарейсы. Если есть рейс из города A в город B, то есть рейс из города B в город A.

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

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

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

В первой строке содержится единственное целое число N (2 ≤ N ≤ 1000). Далее следует N вещественных чисел с точностью не более шести знаков после десятичной точки, i-ое из которых — температура в i-ом городе.

Все температуры даны в градусах Цельсия и не превышают по абсолютной величине 45. Далее следует целое неотрицательное число M — число авиарейсов (не более 105). Далее следует M строк по два целых положительных числа — номера городов, которые соединяет очередной рейс.

Никакой рейс не соединяет город сам с собой. Между двумя городами не может быть более одного рейса.

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

Если добраться до города с номером N из города номер 1 невозможно, выведите «Impossible» (без кавычек), иначе в единственной строке выведите вещественное неотрицательное число — минимально возможный максимальный перепад температуры с ровно шестью знаками после десятичной точки.

Примеры
Стандартный вводСтандартный вывод
4
10
20.2
15.1
20.5
5
1 2
2 3
2 4
1 4
1 3
5.100000