Rezolvare PBinfo #1462

În orașul Nicăieri există N băieți răi. Se știe că între ei există M relații de prietenie. De-a lungul timpului, aceste prietenii au dus la apariția unor “găști”. Dacă doi băieți nu sunt prieteni dar au cel puțin un prieten comun spunem că “se cunosc”. Dacă doi băieți au cel puțin o cunoștință comună, atunci și ei se cunosc. O gașcă este un grup de băieți cu proprietatea că oricare ar fi doi băieți x și y din grup, aceștia “se cunosc”.

Cerința

Arpsod, știe exact cine este prieten cu cine și, fiind singurul băiat bun din oraș, și-a pus următoarele întrebări:
1. Câte găști există în oraș.
2. Dacă ar mai exista O SINGURĂ relație de prietenie pe lângă cele date, în câte moduri ar putea apărea aceasta, astfel încât să se obțină o gașcă cu număr maxim de membri. Pentru că numărul de moduri poate fi foarte mare, Arpsod se mulțumește cu restul împărțirii rezultatului la 666013.

Pentru că e prea ocupat să se baricadeze în casă de frica băieților răi, Arpsod vă roagă pe voi să aflați cele două răspunsuri

Date de intrare

Pe prima linie a fișierului gasti.in se vor afla două numere naturale N și M reprezentând numărul de băieți răi, respectiv numărul de relații de prietenie. Următoarele M linii vor conține câte două numere naturale x și y cu semnificația că există o relație de prietenie între băiatul x și băiatul y.

Date de ieșire

Pe singura linie a fișierului gasti.out se vor afișa două numere separate prin spațiu, primul reprezentând răspunsul pentru prima cerința iar cel de-al doilea pentru a doua cerință.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 0 ≤ M ≤ 300.000
• Dacă x este prieten cu y atunci și y este prieten cu x
• Toate relațiile de prietenie sunt unice
• La numărarea modurilor de adaugare a unei prietenii, prietenia x y si prietenia y x coincid
• Se garanteaza ca pentru 30% din teste 1 ≤ N ≤ 1000
• Pentru rezolvarea corectă a primei cerințe se acordă 40% din punctajul pe testul respectiv iar pentru rezolvarea corectă a celei de-a doua cerințe se acordă 60% din punctajul pe testul respectiv
• Fișierul de ieșire TREBUIE să conțină DOUĂ valori chiar dacă doriți să rezolvați o singură cerință din cele două
• Arpsod înțelege cel mai bine hit-ul lui Bob Marley: “Bad Boys”

Exemplu:

gasti.in

5 3
1 2
2 3
3 1

gasti.out

3 6

Explicație

Există 3 găști în oraș, formate:

Gașca 1: 1, 2, 3
Gașca 2: 4
Gașca 3: 5

Sunt 6 moduri de a face o relație de prietenie astfel încât gașca obținută să aibă număr maxim de membri

4 cu 1, 4 cu 2, 4 cu 3, 5 cu 1, 5 cu 2, 5 cu 3