Farmer John hat $N$ Weiden ($1 \leq N \leq 50,000$), nummeriert $1...N$, verbunden durch $M$ bidirektionale Wege ($1 \leq M \leq 100,000$). Weg $i$ verbindet $A_i$ ($1 \leq A_i \leq N$) mit $B_i$ ($1 \leq B_i \leq N$), mit $A_i != B_i$. Zwei Wege dürfen dasselbe Paar verbinden.
Bessie dekoriert für FJs Geburtstag. Sie will auf jeder Weide ein großes Schild '$F$' oder '$J$', aber um FJ nicht zu verwirren, müssen durch einen Weg verbundene Weiden verschiedene Buchstaben haben.
Die Firma verlangt für '$F$' mehr als für '$J$', daher maximiert Bessie die Anzahl '$J$'. Bestimme sie oder gib -1 aus, wenn keine gültige Anordnung existiert.
Eingabe
- Zeile 1: ganze Zahlen $N$ und $M$.
- Zeilen $2..M+1$: ganze Zahlen $A_i$ und $B_i$, ein bidirektionaler Weg zwischen $A_i$ und $B_i$.
Ausgabe
- Zeile 1: ganze Zahl, maximale Anzahl '$J$'-Schilder. Gibt es keine gültige Lösung, gib -1 aus.
Beispiele
Eingabe 1
4 4 1 2 2 3 3 4 4 1
Ausgabe 1
2
Hinweis
Weiden und Wege bilden die Ecken und Seiten eines Quadrats.
Bessie kann '$J$' auf Weiden 1 und 3 oder alternativ 2 und 4 setzen.
Aufgabenautor: Kalki Seksaria, 2014