Вам дан граф из \(n\) вершин и \(m\) ориентированных дуг. Дуга под номером \(i\) идет из вершины \(x_i\) в вершину \(y_i\), имеет пропускную способность \(c_i\) и вес \(w_i\). Ни одна дуга не входит в вершину \(1\); также ни одна дуга не выходит из вершины \(n\). В графе нет циклов отрицательного веса (невозможно переместиться из вершины в нее же саму таким образом, что суммарный вес всех ребер, которые мы прошли, будет отрицательным).
Вы должны каждой дуге назначить величину потока (целое число между \(0\) и пропускной способностью дуги, включительно). Для каждой вершины, кроме \(1\) и \(n\), суммарная величина потока на дугах, входящих в нее, должна быть равна суммарной величине потока на дугах, исходящих из нее. Пусть величина потока на \(i\)-й дуге равна \(f_i\), тогда стоимость потока можно вычислить как \(\sum \limits_{i = 1}^{m} f_i w_i\). Вам нужно найти комбинацию величин потока, которая минимизирует стоимость.
Говорите, это баян? Ну, у нас есть дополнительные ограничения на поток по каждой дуге:
- если \(c_i\) — четное число, \(f_i\) тоже должна быть четным числом;
- если \(c_i\) — нечетное число, \(f_i\) тоже должна быть нечетным числом.
Получится ли у вас решить эту задачу?
Выходные данные
Если потока, удовлетворяющего ограничениям задачи, не существует, выведите Impossible.
Иначе выведите две строки:
- в первой строке должно быть одно слово Possible;
- во второй строке — \(m\) целых чисел \(f_1, f_2, \dots, f_m\).
Если ответов несколько, выведите любой из них. Обратите внимание, что вы должны минимизировать стоимость потока.