Az I/S. 65. feladat (2022. október)

I/S. 65. Adott egy $\displaystyle N$ csúcsból és $\displaystyle M$ élből álló irányítatlan gráf. A csúcsokat $\displaystyle 1$-től $\displaystyle N$-ig indexeljük. A gráfot az alábbi módon több lépésben bővítjük élek hozzáadásával: egy lépésben keresünk egy olyan $\displaystyle x$ és $\displaystyle y$ csúcspárt, amely nincs összekötve, de létezik olyan $\displaystyle z$ csúcs, ami össze van kötve $\displaystyle x$-szel és $\displaystyle y$-nal is ($\displaystyle 1\le x,y,z\le N$). Ha találtunk ilyen $\displaystyle x, y$ csúcspárt, akkor összekötjük őket egy éllel, ha nem, akkor befejeződött a gráf bővítése.

Adjuk meg, hogy a gráfbővítés befejeztével hány él van a gráfban. Mivel ez a szám nagyon nagy is lehet, ezért a szám $\displaystyle (10^{9}+7)$-tel vett osztási maradékát kell megadni.

A standard bemenet első sorában az $\displaystyle N$ és $\displaystyle M$ számok szerepelnek szóközzel elválasztva. A további $\displaystyle M$ sor mindegyike 2 számot tartalmaz szóközzel elválasztva: egy adott él két végpontjának indexét.

A standard kimenet egyetlen sorában egy szám szerepeljen: a gráfbővítés befejeztével a gráfban levő élek száma modulo $\displaystyle 10^{9}+7$.

Korlátok: $\displaystyle 2 \le N,M \le 10^{5}$. Időlimit: 0,4 mp.

Értékelés: a pontok 50%-a kapható, ha a program az $\displaystyle N,M \le 500$ tesztesetekre helyes kimenetet ad.

(10 pont)

A beküldési határidő 2022. november 15-én LEJÁRT.

Statisztika:

8 dolgozat érkezett.
10 pontot kapott:	Veres Benedek Zoltán, Zádor-Nagy Zsombor.
9 pontot kapott:	Szabó Imre Bence.
5 pontot kapott:	2 versenyző.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2022. októberi informatika feladatai