Influencer

influencer

h2. Date de intrare

Fişierul de intrare $influencer.in$ conţine pe prima linie două numere naturale $N$ şi $M$, separate printr-un spaţiu. Pe următoarele $M$ linii se vor afla câte două numere naturale $u$ şi $v$, separate printr-un spaţiu, reprezentând o legătură specială bidirecţională între influencerul $u$ şi $v$.

Fişierul de intrare $influencer.in$ conţine pe prima linie două numere naturale $N$ şi $M$, separate printr-un spaţiu.
Pe următoarele $M$ linii se vor afla câte două numere naturale $u$ şi $v$, separate printr-un spaţiu, reprezentând o legătură specială bidirecţională între influencerul $u$ şi $v$.

h2. Date de ieşire

h2. Restricţii
* $3 ≤ N ≤ 1 000 000$

* $0 ≤ M ≤ [N/2]$, unde $[x]$ reprezintă parte întreagă din $x$

* $0 ≤ M ≤ [N/2]$, unde [x] reprezintă parte întreagă din x

* Pentru orice legătură specială $(u, v)$, se garantează că $|u - v| ≥ 2$ şi perechea nu este $(0, N - 1)$ (nodurile nu sunt adiacente pe cerc).
table(example). |_. # |_. Punctaj |_. Restricţii |

h3. Explicaţie

Avem $N = 4$ influenceri şi o singură legătură $(M = 1)$ specială bidirecţională între influencerul $0$ şi $2$. Această coardă împarte cercul în două jumătăţi care devin independente din punct de vedere al conectivităţii faţă de ansamblul ${0, 2}$: calea prin utilizatorul $1$ şi calea prin utilizatorul $3$.

Avem $N=4$ influenceri şi o singură legătură $(M = 1)$ specială bidirecţională între influencerul $0$ şi $2$. Această coardă împarte cercul în două jumătăţi care devin independente din punct de vedere al conectivităţii faţă de ansamblul ${0, 2}$: calea prin utilizatorul $1$ şi calea prin utilizatorul $3$.

Pentru ca întreaga reţea să fie tare conexă, este suficient şi necesar ca influencerul $1$ şi $3$ să poată trimite şi primi mesaje de la mulţimea ${0, 2}$.