Банки#13003

Банки

3 секунди
512 мегабайтів
Дуже складна

Том і Джеррі несподівано стали керувати мережею банків!

Банки з’єднані дорогами, які утворюють дерево — тобто між будь-якими двома банками існує рівно один шлях. Серед усіх банків є два центральні: один належить Тому, а інший — Джеррі. Обидва центральні банки можуть друкувати гроші. Гарантовано, що центральні банки Тома та Джеррі безпосередньо з’єднані однією дорогою.

Після перевірки системи Том і Джеррі виявили, що всі банки повністю порожні. Тому вони склали план, скільки грошей має бути в кожному банку на початок року. Зокрема, в -му банку має опинитися рівно a_i доларів. Кожному банку потрібні кошти для роботи, тому всі значення a_i є додатними.

Необхідно виконати цей план таким чином:

Визначте, скільки доларів мають надрукувати Том і Джеррі, та побудуйте послідовність переказів, яка забезпечить виконання плану. Якщо це неможливо, виведіть impossible.

Вхідні дані

У першому рядку задано ціле число — кількість банків.

У другому рядку задано два цілі числа — номери центральних банків (від до включно). Гарантовано, що вони різні та безпосередньо з’єднані дорогою.

У кожному з наступних (n - 1) рядків задано по два цілі числа та — банки, з’єднані дорогою.

В останньому рядку задано додатних цілих чисел a_1, a_2, \dots, a_n — кількість доларів, яку повинен отримати кожен банк.

2 \le n \le 4000,

1 \le a_i \le 10^9.

Вихідні дані

Якщо виконати план неможливо, виведіть impossible.

Інакше в першому рядку виведіть два цілі числа — кількість доларів, яку повинні надрукувати перший і другий центральні банки відповідно.

У другому рядку виведіть ціле число — кількість переказів (0 \le k \le n).

У кожному з наступних рядків виведіть по три цілі числа , та , які означають, що необхідно переказати доларів з банку до банку . Перекази слід виводити в порядку їх виконання.

Якщо існує декілька правильних відповідей, виведіть будь-яку з них.

Приклади

Приклад

Loading
Loading