F. MCF
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан граф из $$$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$$$ тоже должна быть нечетным числом.

Получится ли у вас решить эту задачу?

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

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 100$$$; $$$1 \le m \le 200$$$).

Затем следуют $$$m$$$ строк. В $$$i$$$-й из них заданы четыре целых числа $$$x_i$$$, $$$y_i$$$, $$$c_i$$$ и $$$w_i$$$ ($$$1 \le x_i \le n - 1$$$; $$$2 \le y_i \le n$$$; $$$x_i \ne y_i$$$; $$$1 \le c_i \le 100$$$; $$$-100 \le w_i \le 100$$$). Эти числа описывают $$$i$$$-ю дугу.

Дополнительные ограничения на входные данные:

  • в графе нет циклов отрицательного веса.
Выходные данные

Если потока, удовлетворяющего ограничениям задачи, не существует, выведите Impossible.

Иначе выведите две строки:

  • в первой строке должно быть одно слово Possible;
  • во второй строке — $$$m$$$ целых чисел $$$f_1, f_2, \dots, f_m$$$.

Если ответов несколько, выведите любой из них. Обратите внимание, что вы должны минимизировать стоимость потока.

Примеры
Входные данные
3 3
1 2 3 -10
1 2 3 -15
2 3 2 0
Выходные данные
Possible
1 1 2
Входные данные
3 3
1 2 3 -10
1 2 3 -15
2 3 3 0
Выходные данные
Impossible
Входные данные
3 3
1 2 3 -10
1 2 3 -15
2 3 4 0
Выходные данные
Possible
1 3 4
Входные данные
6 7
5 6 9 -40
1 2 3 -10
1 4 5 20
4 5 7 30
2 5 1 -15
1 3 3 5
3 5 3 0
Выходные данные
Possible
5 1 1 1 1 3 3