Maksimal axınların ölçüsü

Atsikllik yönləndirilmiş qraf G-yə baxaq, burada hər bir kənarın uv keçirmə qabiliyyəti c(uv) ilə təyin olunur. G-də iki xüsusi zirvə var: mənbə s və axın t.

G-də axın f : E -> R funksiyası adlanır, əgər aşağıdakı şərtlər yerinə yetirilirsə:

1. Bütün kənarlar uv üçün 0 ≤ f(uv) ≤ c(uv).

2. s və t istisna olmaqla hər bir zirvə u üçün

Axın f-in böyüklüyü |f| ilə işarələnir və bu, mənbədən çıxan axının miqdarını göstərir:

Axın maksimal adlanır, əgər |f| G-dəki bütün axınlar arasında mümkün olan ən böyükdür. Bir neçə maksimal axın mövcud ola bilər.

Axınlar digər funksiyalar kimi nöqtə-nöqtə toplana və ya real sabitə vurula bilər. Müəyyən bir maksimal axın f[max]-i sabitləyək. Axınlar çoxluğu {f[1], f[2], ..., f[n]} maksimal axınların bazisini təşkil edir deyilir, əgər hər bir maksimal axın

şəklində təqdim edilə bilərsə və onun heç bir alt çoxluğu bu xüsusiyyətə malik deyilsə. Burada a[i] R-ə aiddir.

Bu çoxluğun ölçüsü - n - qrafın maksimal axınlarının ölçüsü adlanır.

Verilmiş qraf G üçün onun maksimal axınlarının ölçüsünü tapın.

Giriş məlumatları

Birinci sətir qrafın zirvələrinin və kənarlarının sayını (1 ≤ n ≤ 10, 1 ≤ m ≤ 10) - n və m ehtiva edir. Növbəti m sətirin hər biri üç tam ədəd ehtiva edir və kənarları təsvir edir. Hər bir kənar çıxış zirvəsi, giriş zirvəsi və onun keçirmə qabiliyyəti ilə təsvir olunur. Qraf atsikllikdir. Mənbə 1 nömrəsinə, axın isə n nömrəsinə malikdir. Keçirmə qabiliyyətləri 10^4-ü keçmir. Mənbədən axına yolun mövcudluğu təmin edilir.

Çıxış məlumatları

Verilmiş qrafın maksimal axınlarının maksimal ölçüsünü çıxarın.