eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Размерность максимальных потоков

Размерность максимальных потоков

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Рассмотрим ациклический ориентированный граф G, с каждым ребром которого uv связана пропускная способность c(uv). Пусть G имеет две специальные вершины: исток s и сток t.

Потоком в G называется функция f : E -> R такая что следующие условия имеют место:

  1. 0f(uv) ≤ c(uv) для всех ребер uv.

  2. для всякой вершины u кроме s и t

prb8484.gif

Величина потока f обозначается как |f| - количество потока, исходящего из истока:

prb8484_1.gif

Поток называется максимальным если |f| наибольшее возможное среди всех потоков в G. Очевидно, что может существовать несколько максимальных потоков.

Потоки могут быть сложены поточечно или умножены на действительную константу, как и на любые другие функции. Зафиксируем некоторый максимальный поток f[max]. Говорят, что множество потоков {f[1], f[2], ..., f[n]} образуют базис максимальных потоков, если каждый максимальный поток можно представить в виде суммы

prb8484_2.gif

и никакое его подмножество не имеет этого свойства. Здесь a[i] принадлежит R.

Размер этого множества - n - называется размерностью максимальных потоков графа.

По заданному графу G найдите размерность его максимальных потоков.

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

Первая строка содержит n и m - количество вершин и ребер в графе (1n10, 1m10). Каждая из следующих m строк содержит три целых числа и описывает ребра. Каждое ребро описывается исходящей вершиной, входящей вершиной и его пропускной способностью. Граф ациклический. Исток имеет номер 1, сток имеет номер n. Пропускные способности не превосходят 10^4. Гарантируется, что существует путь из истока в сток.

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

Выведите максимальную размерность максимальных потоков заданного графа.

Пример

Входные данные #1
2 1
1 2 1
Выходные данные #1
0
Входные данные #2
4 5
1 2 2
1 3 2
3 2 1
2 4 2
3 4 1
Выходные данные #2
1
Источник 2007 Petrozavodsk, Andrew Stankevich Contest 22, January 27, Problem A