Острівні держави#1938
У буремну феодальну епоху колись могутня острівна держава Байтландія була під владою двох могутніх баронів, кожен з яких контролював частину міст. Деякі міста з'єднані двосторонніми дорогами. Для проїзду по дорозі, що з'єднує міста, які контролюють різні барони, необхідно сплатити збір у розмірі одного байтландського рубля. Окрім цього, за виїзд з міста з парним номером стягується подвійний збір.
Програміст Вася мешкає у місті . З настанням літа він планує дістатися до міста на Зустріч Програмістів Байтландії. Він хоче витратити на цю подорож якомога менше грошей і звертається до вас по допомогу.
У першому рядку задано два цілих числа та (1 \leq n, m \leq 100000) — кількість міст та кількість доріг.
У наступному рядку задано цілих чисел: або — який барон контролює кожне місто.
Далі йдуть рядків, у кожному з яких по два цілих числа та (1 \leq a, b \leq n, a \neq b), що описують дорогу між містами та . Всі дороги — двосторонні.
Якщо дістатися неможливо, виведіть одне слово impossible. Інакше в першому рядку виведіть мінімальну вартість та кількість відвіданих міст. У другому рядку виведіть міста в порядку відвідин. Якщо існує кілька шляхів з мінімальною вартістю, виведіть будь-який з них.
Приклад 1