Adott egy $N$ csúcsú, $M$ élű egyszerű gráf (nincs többszörös él vagy hurokél, de nem feltétlenül összefüggő). A csúcsokat 0-tól $\left(N-1\right)$-ig indexeljük. A gráf összes csúcsa fekete vagy fehér. Jelölje $f\left(x\right)$ az $X$ csúcs színét. Cseresznyének hívunk egy $\left(A\mathrm{,}B\mathrm{,}C\right)$ rendezett csúcshármast, ha páronként különbözőek és létezik az $A-B$, valamint a $B-C$ csúcspárok közt él. Egy $\left(A\mathrm{,}B\mathrm{,}C\right)$ cseresznye finom, ha $f\left(A\right)=f\left(C\right)$ és $f\left(A\right)\ne f\left(B\right)$. Adjuk meg, hogy egy él behúzásával legföljebb mennyire növelhető a finom cseresznyék száma. ($A$ és $B$ csúcs összeköthető egy éllel, ha $A\ne B$, és eddig nem létezett köztük él.)
Standard bemenet: az első sor tartalmazza $N$-et és $M$-et. A következő sor $N$ darab számot tartalmaz: az $i$-edik szám az $i-1$ indexű csúcs színét határozza meg, 0 ha fekete, 1 ha fehér. A következő $M$ sor mindegyike két számot tartalmaz. Az $i$-edik sor az $i$-edik él két végpontjának csúcsindexét adja meg.
Standard kimenet: a maximálisan elérhető finom cseresznyék száma.
Korlátok: $3\le N\le {10}^5$, $0\le M\le \underset{}{\overset{}{\text{min}}}\left({10}^5\mathrm{,}{N}^2-N-1\right)$. Időkorlát: 0,3 mp.
Értékelés: A pontok 50%-a kapható, ha a gráf fa.
Példa: