Розмірність максимальних потоків
Розгляньмо ациклічний орієнтований граф G, у якому кожне ребро uv має пропускну здатність c(uv). Граф G містить дві спеціальні вершини: витік s і стік t.
Потоком у G називається функція f : E -> R, яка задовольняє такі умови:
0 ≤ f(uv) ≤ c(uv) для всіх ребер uv.
Для кожної вершини u, окрім s і t, виконується:
Величина потоку f позначається як |f| і визначається як кількість потоку, що виходить з витоку:
Потік називається максимальним, якщо |f| є найбільшим серед усіх можливих потоків у G. Можливо, існує кілька максимальних потоків.
Потоки можуть бути складені поточково або помножені на дійсну константу, як і будь-які інші функції. Зафіксуємо деякий максимальний потік f[max]. Кажуть, що множина потоків {f[1], f[2], ..., f[n]} утворює базис максимальних потоків, якщо кожен максимальний потік можна представити у вигляді суми
і жодна його підмножина не має цієї властивості. Тут a[i] належить R.
Розмір цієї множини - n - називається розмірністю максимальних потоків графа.
За заданим графом G знайдіть розмірність його максимальних потоків.
Вхідні дані
Перша строка містить n і m - кількість вершин і ребер у графі (1 ≤ n ≤ 10, 1 ≤ m ≤ 10). Кожен з наступних m рядків містить три цілі числа, що описують ребра. Кожне ребро описується вихідною вершиною, вхідною вершиною та його пропускною здатністю. Граф ациклічний. Витік має номер 1, стік має номер n. Пропускні здатності не перевищують 10^4. Гарантується, що існує шлях з витоку в стік.
Вихідні дані
Виведіть максимальну розмірність максимальних потоків заданого графа.