compeuler

Se dă un graf neorientat prin numărul de noduri $N$, numărul de muchii $M$ și $M$ perechi de noduri repreprezenând muchiile. Nodurile sunt etichetate cu $1, 2, \dots, N$. Dorim să determinăm componentele conexe și să verificăm care dintre ele sunt subgrafuri euleriene.

Cerință

Se dă un graf neorientat prin $N$, $M$ și $M$ perechi de noduri cu semnificația de mai sus și se cere:

1. Numărul maxim de noduri într-o componentă conexă.
2. Numărul de componente conexe care sunt subgrafuri euleriene.

Date de intrare

Pe prima linie a fișierului de intrare compeuler.in se găsește numărul cerinței $C$, pe linia a doua $N$ și $M$ separate printr-un spațiu, iar pe următoarele $M$ linii, perechi de noduri separate prin câte un spațiu reprezenând muchiile.

Date de ieșire

Pe prima linie a fișierului de ieșire compeuler.out se va găsi un singur număr reprezenând numărul maxim de noduri într-o componentă conexă, dacă cerința este $C = 1$, respectiv numărul de componente conexe care sunt subgrafuri euleriene, dacă cerința este $C = 2$.

Restricții și precizări

• $1 \leq N \leq 1 \ 000$;
• $1 \leq M \leq 10 \ 000$;
• Pentru rezolvarea corectă a cerinței $1$ se vor acorda $20$ de puncte.
• Pentru rezolvarea corectă a cerinței $2$ se vor acorda $80$ de puncte.

Exemplul 1

compeuler.in

1
6 4
1 4
5 2
3 2
3 5

compeuler.out

3

Explicație

$C = 1$. Există $3$ componente conexe cu mulțimea nodurilor fiecare: $\{1,4\}$, $\{2,3,5\}$, $\{6\}$. Deci $3$ este numărul maxim de noduri într-o componentă conexă.

Exemplul 2

compeuler.in

2
6 4
1 4
5 2
3 2
3 5

compeuler.out

1

Explicație

$C = 2$. Există $3$ componente conexe cu mulțimea nodurilor fiecare: $\{1,4\}$, $\{2,3,5\}$, $\{6\}$. Dintre aceste $3$ componente conexe, doar a doua este subgraf eulerian.