Module: Floyd-Algorithmus

Es wurde ein orientierter Graph angegeben. Bestimmen Sie, ob ein Zyklus mit negativem Gewicht darin ist, und wenn ja, ziehen Sie ihn ab.

 

Die erste Zeile enthält die Zahl N (1 <= N <= 100) – Anzahl der Eckpunkte des Graphen. In den folgenden N Zeilen befindet sich die N Zahlen – die Adjazenzmatrix des Graphen. Das Gewicht der Rippen ist modular kleiner als 100000. Wenn keine Kante vorhanden ist, ist der entsprechende Wert 100000.

 

Geben Sie in der ersten Zeile "YES" aus, wenn die Schleife existiert, oder "NO", andernfalls. Wenn eine Schleife vorhanden ist, geben Sie in der zweiten Zeile die Anzahl der Scheitelpunkte darin aus (wobei die erste und die letzte gleich sind), und in der dritten Zeile die Scheitelpunkte, die in dieser Schleife enthalten sind, in der Durchforstungsreihenfolge aus. Wenn es mehrere Zyklen gibt, dann  geben Sie eine von ihnen aus.

Beispiele

№	Eingabe	Ausgabe
1	3 100000 100000 -51 100  100000 100000 100000 -50  100000	YES 4 3 2 1 3