# Eulerweg Eulerkreis

# a = [[0] * m for i in range(n)]
# erzeugt eine zweidimensionale Liste mit n
# Komponenten, wobei jede Komponente wiederum
# eine Liste mit m Komponenten ist; jeder 
# Komponente a[i][j], 0 <= i <= n-1, 0 <= j <= m-1, 
# wird der Wert 0 zugewiesen.
# Diese zweidimensionale Liste laesst sich als 
# Matrix mit n Zeilen und m Spalten auffassen.
# i = Zeilenindex, j = Spaltenindex

n = int(input('Anzahl der Knoten: '))

# Erzeugen der n x n - Adjazenzmatrix als 
# zweidimensionale Liste mit lauter Nullen
a = [[0] * n for i in range(n)]

# Erzeugen der Liste g, deren n Komponenten
# g[i], 0 <= i <= n-1, Platzhalter fuer den Grad
# eines jeden Knotens sind.
g = list(range(n))

# Eingabe der Adjazenzmatrix
for i in range(n):
   for j in range(n):
         print('a(',i+1,',',j+1,') = ')
         a[i][j] = int(input())       

# Berechnung des Grades von jedem der n Knoten
for i in range(n): g[i] = 0
for i in range(n):
    for j in range(n): g[i] = g[i] + a[i][j]

# Ausgabe der Adjazenzmatrix
print()
print('Adjazenzmatrix:')
print(a)

# Ausgabe des Grades eines jeden Knotens
print()
print('Grad eines jeden Knotens: ')
print(g)
print()

# Entscheidung gemaess dem Satz von Euler
i = 0
anzahl = 0
while i <= n-1:
    if g[i] % 2 == 1: anzahl = anzahl + 1
    i += 1
if anzahl == 0 or anzahl == 2:
    if anzahl == 0:
        print('Der Grad jedes Knotens ist geradzahlig,')
        print('folglich hat der Graph einen Eulerkreis.')
    if anzahl == 2:
        print('Der Grad von genau zwei Knoten ist ungeradzahlig,')
        print('folglich hat der Graph einen Eulerweg.')
else:
    if anzahl == 1:
        print('Da genau', anzahl, 'Knoten einen ungeraden Grad hat,')
        print('besitzt der Graph weder einen Eulerkreis noch einen Eulerweg.')
    else:
        print('Da', anzahl, 'Knoten einen ungeraden Grad haben,')
        print('besitzt der Graph weder einen Eulerkreis noch einen Eulerweg.')