Se dă un graf neorientat. Se doreşte transformarea acestuia într-un graf orientat prin stabilirea unui sens pentru fiecare muchie a grafului iniţial. Mai exact fiecare muchie [x,y] a grafului iniţial va fi transformată într-un arc de la x la y sau un arc de la y la x. Graful obţinut trebuie să nu aibă circuite şi gradul exterior maxim al unui nod să fie minim.
Cerinţă
Scrieţi un program care să determine gradul exterior maxim al unui nod din graful obţinut după transformarea efectuată în condiţiile din enunţ.
Date de intrare
Fişierul de intrare dag.in conţine pe prima linie numerele naturale n şi m reprezentând numărul de noduri, respectiv numărul de muchii ale grafului iniţial. Pe următoarele m linii se vor afla câte două numere naturale x şi y reprezentând o muchie între nodurile x şi y ale grafului iniţial. Nodurile grafului iniţial sunt numerotate cu numere naturale distincte de la 1 la n.
Date de ieşire
Fişierul de ieşire dag.out va conţine un singur număr natural reprezentând gradul exterior maxim al unui nod din graful obţinut după transformarea efectuată în condiţiile din enunţ.
Restricţii
1 <= n <= 100 000
1 <= m <= 300 000
Între oricare două noduri există cel mult o muchie.
Nu există muchii de la un nod la el însuşi.
Exemple
dag.in
dag.out
Explicaţie
4 5
1 2
1 3
1 4
2 3
3 4
2
O soluţie este să avem arcele: (1,3), (2,1), (2,3), (4,1), (4,3). Graful obţinut nu are circuite, iar gradul exterior maxim este2.