Untitled

import sys

# 1 je igrac
# 2 je komp

def krajIgre(tabla):
    for i in range(3):
        if tabla[i][0] == tabla[i][1] == tabla[i][2] != 0:
            return tabla[i][2]
        if tabla[0][i] == tabla[1][i] == tabla[2][i] != 0:
            return tabla[2][i]
    if tabla[0][0] == tabla[1][1] == tabla[2][2] != 0:
        return tabla[2][2]
    elif tabla[0][2] == tabla[1][1] == tabla[2][0] != 0:
        return tabla[2][0]
    
    proizvod = 1
    for i in range(3):
        for j in range(3):
            proizvod *= tabla[i][j]
    if proizvod:
        return 3
    return 0

def imaNade(tabla):
    brojac = 0
    igrac = 0
    rez = False
    tren = False
    for i in range(3):
        for j in range(3):
            if tabla[i][j] != 0:
                brojac += 1
    
    igrac = 1 if brojac % 2 == 0 else 2

    for i in range(3):
        for j in range(3):
            if tabla[i][j] == 0:
                tabla[i][j] = igrac
                tren = imaNade(tabla)
                tabla[i][j] = 0
                if tren:
                    rez = True
    
    if brojac == 9:
        if krajIgre(tabla) == 3:
            return False
        return True
    return rez

def ispisi(tabla):
    for i in range(3):
        for j in range(3):
            print(tabla[i][j], end=" ")
        print()

def rekurzija(tabla, dubina=0):
    rez = float('-inf') if dubina % 2 else float('inf')
    tren = 0

    if not krajIgre(tabla):
        for i in range(3):
            for j in range(3):
                if tabla[i][j] == 0:
                    tabla[i][j] = 2 if dubina % 2 else 1
                    tren = rekurzija(tabla, dubina + 1)
                    tabla[i][j] = 0
                    if dubina % 2 and tren > rez:
                        rez = tren
                    if dubina % 2 == 0 and tren < rez:
                        rez = tren
        return rez
    elif krajIgre(tabla) == 1:
        return -1
    elif krajIgre(tabla) == 2:
        return 1
    else:
        return 0

def najboljiPotez(tabla):
    najRez = -5
    rez = 0
    pozicija = 0
    for i in range(3):
        for j in range(3):
            if tabla[i][j] == 0:
                tabla[i][j] = 2
                rez = rekurzija(tabla)
                if rez > najRez:
                    najRez = rez
                    pozicija = i * 3 + j + 1
                if krajIgre(tabla) == 2:
                    najRez = rez
                    pozicija = i * 3 + j + 1
                tabla[i][j] = 0
    return pozicija

def unosenjePoteza(tabla):
    br = 0
    while not krajIgre(tabla) and imaNade(tabla):
        ispisi(tabla)
        br = int(input())
        br -= 1
        tabla[br // 3][br % 3] = 1

        if krajIgre(tabla) == 1:
            print("Pobedio si!")
        elif krajIgre(tabla) == 3:
            print("Nereseno!")
        elif not imaNade(tabla):
            ispisi(tabla)
        elif imaNade(tabla):
            br = najboljiPotez(tabla)
            br -= 1
            tabla[br // 3][br % 3] = 2
            if not imaNade(tabla):
                ispisi(tabla)

        if krajIgre(tabla) == 2:
            print("Izgubio si!")
        if not imaNade(tabla):
            print("Nereseno!")


tabla = [[0 for _ in range(3)] for _ in range(3)]
unosenjePoteza(tabla)