n təpəsi, k tili olan dövri olmayan istiqamətlənmiş qraf verilmişdir. Onun tranzitiv qapanmasındakı tillərinin sayını tapın.
G qrafının tranzitiv qapanması – verilmiş G qrafının təpələr çoxluğundan və tillər (u, v) çoxluğundan ibarət olan elə G' qrafıdır ki, ilkin G qrafında həmişə u təpəsindən v təpəsinə yol mövcud olsun.
Knut məsələnin həllini bilir, bəs Siz?
İlk sətirdə n və k (1 ≤ n, k ≤ 50000) ədədləri verilib. Hər sonrakı k sətirdə a[i]
təpəsi ilə b[i]
təpəsi arasında tilin mövcudluğunu göstərən iki a[i]
və b[i]
(1 ≤ a[i]
, b[i]
≤ n) tam ədədləri verilir. Qraf ilgək, dövrlər, bölünən tillər ehtiva etmir.
Tranzitiv qapanmadakı tillərin sayını verməli.