Problem I
Liebespolygon

Wie wir alle wissen, können Seifenopern mit vielen Protagonisten zu ernsthaft komplizierten Liebesdramen führen. In einer TV-Serie gibt es $N$ Protagonisten. Jeder Protagonist liebt exakt einen anderen Protagonisten (möglicherweise auch sich selbst). Zwei Protagonisten sind in einer Liebesbeziehung genau dann, wenn sie sich gegenseitig lieben.

Ein besonders komplizierter Beziehungstyp ist ein “Liebespolygon”. 3 oder mehr Protagonisten sind in einem “Liebespolygon”, wenn der erste Protagonist den zweiten liebt, der zweite Protagonist den dritten und so weiter, und der letzte Protagonist auch den ersten liebt.

Neue Umfragen haben gezeigt, dass Fernsehzuschauer von diesem Drama gelangweilt sind und etwas romantischeres bevorzugen würden. Daher wurde entschieden, einige Protagonisten mit Liebespfeilen zu beschießen, sodass jeder in einer Liebesbeziehung ist. Jemanden mit einem Liebespfeil zu beschießen, ermöglicht dir, zu bestimmen, wen der Protagonist liebt.

Wie viele Liebespfeile werden mindestens benötigt, bis jeder in einer Liebesbeziehung ist?

Eingabe

Die erste Zeile der Eingabe enthält eine ganze Zahl $N$, die Anzahl der involvierten Protagonisten. Die nächsten $N$ Zeilen enthalten jeweils zwei durch Leerzeichen getrennte Namen $s$ und $t$, die bedeuten, dass der Protagonist mit Namen $s$ zu Beginn den mit Namen $t$ liebt. Die Namen der Protagonisten sind nicht länger als $10$ Zeichen und bestehen nur aus englischen Kleinbuchstaben.

Ausgabe

Gib eine ganze Zahl aus: Die minimale Anzahl von Liebespfeilen, die benötigt werden, bis jeder in einer Liebesbeziehung ist. Falls das nicht möglich ist, gib $-1$ aus.

Beschränkungen

Deine Lösung wird auf mehreren Testgruppen ausgeführt werden, von denen jede eine bestimmte Punktzahl wert ist. Jede Testgruppe enthält mehrere Testcases. Um Punkte für eine Testgruppe zu bekommen, müssen alle Testfälle in der entsprechenden Gruppe gelöst werden. Deine finale Punktzahl wird die maximal erreichte Punktzahl in einer einzelnen Einsendungen sein.

Beschreibung der Beispiele

Das erste Beispiel ist in der Abbildung oben dargestellt. Der obere Teil zeigt die Situation zu Beginn, wobei ein Pfeil von $s$ nach $t$ angibt, dass $s$ zu Beginn $t$ liebt. Die rosa Farbe gibt an, welche Protagonisten in der eindeutigen optimalen Lösung mit Liebespfeilen beschossen werden müssen. Der untere Teil zeigt die Situation nachher.

Im zweiten Beispiel (welches die Beschränkungen der Gruppe 3 erfüllt), gibt es mehrere optimale Lösungen. Eine davon ist es, die Protagonisten a, b und d mit Liebespfeilen zu beschießen, und in b, a und c zu verlieben.

Im dritten Beispiel gibt es ein Liebesdreieck. Unabhängig davon, wie viele Liebespfeile wir verschießen, wird immer jemand alleine bleiben.

8
leonard emmy
ada emmy
isaac leonard
emmy pierre
pierre bernhard
bernhard emmy
sofia karl
karl sofia

3

4
a c
b c
c d
d d

3

3
rocky scarlet
scarlet patrick
patrick rocky

-1