LED-схема
Ви відповідаєте за підготовку конференц-залу для закриття церемонії ACM ICPC. Ви найняли перфекціоніста-сентиментального дизайнера приміщень, щоб створити елегантне оформлення для старого залу. Церемонія почнеться за кілька годин, і дизайнер щойно повідомив вас про завершення декорації. Коли ви приходите до конференц-залу, ви стикаєтеся з дивним контуром на стіні. Дизайнер починає пояснювати сенс життя та ACM ICPC, прихований під кожною частиною контуру. Контур складається з світлодіодів (LED), з'єднань та проводів. Ви запитуєте, чи потрібно вмикати світлодіоди. "Звичайно!" відповідає дизайнер, "Кожен світлодіод повинен світитися, інакше вся робота - марна!" Ви оглядаєте контур, щоб знайти його розетку.
- Де розетка?
- Га? Це поза межами моєї роботи! Це ви повинні забезпечити електрику для світлодіодів. І будьте обережні! Не видаляйте і не змінюйте жодної частини контуру; просто підключіть кабелі живлення до з'єднань. Я мушу йти зараз. Я надішлю звіт про свою ідеальну роботу вашому менеджеру. До побачення.
Залишившись наодинці з дивним контуром, ви починаєте його оглядати.
На відміну від ламп розжарювання, які випромінюють світло незалежно від електричної полярності, світлодіоди випромінюють світло лише при правильній електричній полярності (тобто, коли їх анодний контакт має вищий електричний потенціал, ніж катодний контакт). Кожен світлодіод має мінімальну напругу. Світлодіод не випромінює (навіть при правильній полярності), якщо різниця електричних потенціалів його контактів менша за його мінімальну напругу. Кожен світлодіод також має максимальну напругу. Світлодіод знищується, якщо різниця електричних потенціалів перевищує його максимальну напругу.
Ваш огляд контуру показує, що він складається з трьох типів компонентів:
- Світлодіоди: На щастя, всі світлодіоди в контурі одного типу, і тому мають однакову мінімальну напругу та однакову максимальну напругу.
- З'єднання: Кожен з двох контактів світлодіода в контурі підключений до з'єднання. З'єднання не тільки місце для підключення контактів світлодіодів, але й для підключення кінців проводів.
- Проводки: Кожен провід має два кінці і з'єднує з'єднання безпосередньо з іншим з'єднанням, змушуючи їх мати однаковий електричний потенціал.
Підключаючи зовнішні електричні полюси (з різними значеннями напруги) до кожного з'єднання контуру, ви можете вводити різні електричні потенціали до з'єднань. Зверніть увагу на короткі замикання: кінці кожного проводу ПОВИННІ мати однаковий електричний потенціал. За домовленістю, ми можемо вважати мінімальний електричний потенціал рівним нулю. Отже, всі електричні потенціали можуть вважатися невід'ємними.
Тепер ви повинні придбати зовнішнє джерело живлення, яке забезпечить вас необхідними електричними полюсами. Вартість таких джерел живлення залежить від їх верхньої межі: максимальної напруги, яку вони забезпечують.
З огляду на специфікацію світлодіодного контуру, ви повинні написати програму, яка перевіряє, чи можливо запалити всі світлодіоди правильно (без коротких замикань і без знищення світлодіодів). У разі можливості програма також повинна обчислити мінімальну можливу верхню межу джерела живлення, з якою всі світлодіоди можуть світитися.
Вхідні дані
Вхід складається з кількох тестових випадків. Кожен тестовий випадок описує світлодіодний контур і починається з рядка, що містить 5 розділених пробілами цілих чисел J, L, W, m і M, де J - кількість з'єднань (2 ≤ J ≤ 500), L - кількість світлодіодів (1 ≤ L ≤ 5000), W - кількість проводів (0 ≤ W ≤ 5000), а m і M - мінімальна та максимальна напруга світлодіодів відповідно (1 ≤ m < M ≤ 1000). Припустимо, що з'єднання пронумеровані від 1 до J.
Кожен з наступних L рядків представляє світлодіод з двома розділеними пробілами цілими числами. Перше число - номер з'єднання, до якого підключений анодний контакт світлодіода, а друге число - номер з'єднання для катодного контакту. Потім слідують W рядків, кожен з яких описує провід контуру за допомогою двох розділених пробілами цілих чисел: з'єднання, які провід безпосередньо з'єднує.
Вхід завершується рядком, що містить "0 0 0 0 0" (без лапок).
Вихідні дані
Напишіть один рядок виходу для кожного тестового випадку. Якщо немає способу правильно запалити всі світлодіоди в контурі цього тестового випадку, напишіть лише слово "Impossible" (без лапок). В іншому випадку напишіть одне ціле число: мінімальну верхню межу джерела живлення, з якою всі світлодіоди можуть світитися.