# Eulerweg Eulerkreis

# a = [[0] * m for i in range(n)]
# erzeugt eine zweidimensionale Liste mit n
# Komponenten, wobei jede dieser Komponenten ihrerseits
# eine Liste mit m Komponenten ist; jede Komponente
# a[i][j], 0 <= i <= n-1, 0 <= j <= m-1, 
# erhaelt den Wert 0 zugewiesen.

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

# Erzeugen einer n x n - Matrix mit lauter Nullen
a = [[0] * n for i in 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())

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

# Berechnung des Grades von jedem der n Knoten
# Der Grad eines jeden der n Knoten wird in der
# aus n Komponenten bestehenden Liste g abgelegt.
g = [0]*n   # Erzeugen der Liste g mit lauter Nullen
for i in range(n):
   for j in range(n): g[i] = g[i] + a[i][j]

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


# Entscheidung gemaess dem Satz von Euler
anzahl = 0
for i in range(n):
   if g[i] % 2 != 0: anzahl = anzahl + 1

if anzahl == 0 or anzahl == 2:
    if anzahl == 0:
      print('Der Grad jedes Knotens ist geradzahlig,')
      print('folglich hat der Graph einen Eulerkreis.')
    else:
      print('Der Grad von genau zwei Knoten ist ungerade,')
      print('folglich besitzt der Graph einen Eulerweg,');
      print('aber keinen Eulerkreis.')
else:
    if anzahl == 1: print('Da ',anzahl,' Knoten einen ungeraden Grad hat,')
    else:           print('Da ',anzahl,' Knoten einen ungeraden Grad haben,')

    print('besitzt der Graph weder einen Eulerkreis noch einen Eulerweg.')