Tuzgurel este programator web, ultimul site la care lucreaza fiind chiar site-ul ONI 2010.
Site-ul este format din n pagini, iar între pagini existând m legături (links) astfel încât dacă se pleacă dintr-o pagină dând click pe legături nu se va putea ajunge înapoi la pagina inţială.
Tuzgurel vrea să elimine anumite legături astfel încât site-ul să poată fi impărţit într-un număr minim de lanţuri de pagini, fiecare pagină cat si fiecare legătură aparţinând exact unui singur lanţ.
Cerinţă
Determinaţi numărul minim de lanţuri ce se pot obţine.
Date de intrare
Fişierul de intrare site.in va conţine pe prima linie numerele naturale n şi m, reprezentând numărul de pagini respectiv numărul de legături. Pe următoarele m linii se vor afla câte două numere naturale p si q reprezentând legătura dintre paginile p şi q (din pagina p există legătură spre pagina q) .
Date de ieşire
Fişierul de ieşire site.out va conţine o singură linie pe care va fi scris numărul natural P reprezentând numărul minim de lanţuri.
Restricţii
1 ≤ n ≤ 20 000
1 ≤ m ≤ 50 000
Pentru 40% din teste 1 ≤ n ≤ 400, 1 ≤ m ≤ 2 000
Pentru 70% din teste 1 ≤ n ≤ 5 000, 1 ≤ m ≤ 10 000
O legătură p -> q apare cel mult o dată.
Exemple
site.in
site.out
Explicatie
7 11
1 2
1 5
2 3
2 5
2 7
3 4
3 6
4 6
5 4
5 6
7 3
2
Solutii posibile:
lanţul:7-3 lanţul:1-2-5-4-6 sau
lanţul:2-7-3-6 lanţul:1-5-4