import random
import time
import sys
 
sys.setrecursionlimit(10000)
 
def generate_field(N, M, p):
    grid = [[1 if random.random() < p else 0 for _ in range(M)] for _ in range(N)]
    grid[N-1][0] = 0   # старт (лівий нижній)
    grid[0][M-1] = 0   # фініш (правий верхній)
    return grid
 
from collections import deque
def exists_path_bfs(grid):
    N, M = len(grid), len(grid[0])
    start = (N-1,0)
    goal = (0, M-1)
    if grid[start[0]][start[1]] != 0 or grid[goal[0]][goal[1]] != 0:
        return False
    q = deque([start])
    vis = [[False]*M for _ in range(N)]
    vis[start[0]][start[1]] = True
    dirs = [(1,0),(-1,0),(0,1),(0,-1)]
    while q:
        r,c = q.popleft()
        if (r,c) == goal:
            return True
        for dr,dc in dirs:
            nr, nc = r+dr, c+dc
            if 0 <= nr < N and 0 <= nc < M and not vis[nr][nc] and grid[nr][nc] == 0:
                vis[nr][nc] = True
                q.append((nr,nc))
    return False
 
def longest_path_dfs(grid, time_limit=1.5, randomize=True):
    N, M = len(grid), len(grid[0])
    start = (N-1, 0)
    goal = (0, M-1)
    dirs = [(1,0), (0,1), (-1,0), (0,-1)]  
    best_path = None
    best_len = -1
    start_time = time.time()
    max_nodes = 10**6
    nodes = 0
 
    import random as _rnd
 
    visited = [[False]*M for _ in range(N)]
    path = []
 
    def dfs(r,c):
        nonlocal best_len, best_path, nodes
        if time.time() - start_time > time_limit:
            return
        nodes += 1
        if nodes > max_nodes:
            return
 
        if (r,c) == goal:
            if len(path) > best_len:
                best_len = len(path)
                best_path = path.copy()
            return
 
        neighs = []
        for dr,dc in dirs:
            nr, nc = r+dr, c+dc
            if 0 <= nr < N and 0 <= nc < M and not visited[nr][nc] and grid[nr][nc] == 0:
                dist = abs(nr - goal[0]) + abs(nc - goal[1])
                neighs.append((dist, nr, nc))
        neighs.sort(reverse=True, key=lambda x: x[0])
        if randomize:
            i = 0
            while i < len(neighs):
                j = i
                while j < len(neighs) and neighs[j][0] == neighs[i][0]:
                    j += 1
                block = neighs[i:j]
                _rnd.shuffle(block)
                neighs[i:j] = block
                i = j
 
        for _, nr, nc in neighs:
            if time.time() - start_time > time_limit:
                return
            visited[nr][nc] = True
            path.append((nr,nc))
            dfs(nr,nc)
            path.pop()
            visited[nr][nc] = False
 
    if grid[start[0]][start[1]] != 0 or grid[goal[0]][goal[1]] != 0:
        return None
 
    visited[start[0]][start[1]] = True
    path.append(start)
    dfs(start[0], start[1])
    visited[start[0]][start[1]] = False
    path.pop()
 
    return best_path
 
 
def print_board_numbered(grid, path):
    N, M = len(grid), len(grid[0])
    step = {}
    if path:
        for i, cell in enumerate(path):
            step[cell] = i
 
    max_step = max(step.values()) if step else 0
    width = max(3, len(str(max_step)) + 2)
 
    def cell_str(s):
        return str(s).center(width)
 
    print()
    for r in range(N):
        row_cells = []
        for c in range(M):
            if (r,c) in step:
                row_cells.append(cell_str(step[(r,c)]))
            elif grid[r][c] == 1:
                row_cells.append(cell_str("#"))
            else:
                row_cells.append(cell_str("."))
        print("".join(row_cells))
    print()
 
 
def main():
    print("=== Поля і каміння — пошук довгого простого шляху")
    try:
        N = int(input("Введіть кількість рядків N (1..100): ").strip())
        M = int(input("Введіть кількість стовпців M (1..100): ").strip())
    except Exception:
        print("Некоректні N або M.")
        return
    if not (1 <= N <= 100 and 1 <= M <= 100):
        print("N і M повинні бути від 1 до 100.")
        return
 
    try:
        p = float(input("Ймовірність каменю в клітинці (0..1), наприклад 0.25: ").strip())
        if not (0.0 <= p <= 1.0):
            raise ValueError()
    except Exception:
        print("Некоректне p — використовую 0.25")
        p = 0.25
 
    try:
        tlim = float(input("Часовий ліміт пошуку в секундах (наприклад 1.5): ").strip())
        if tlim <= 0:
            tlim = 1.5
    except Exception:
        tlim = 1.5
 
    regen = input("Якщо потрібно — регенерувати поле поки існує шлях? (т/н) [т]: ").strip().lower()
    regen_flag = (regen == "" or regen == "т" or regen == "y" or regen == "yes")
 
    attempts = 0
    while True:
        attempts += 1
        grid = generate_field(N, M, p)
        if exists_path_bfs(grid):
            break
        if not regen_flag:
            break
        if attempts > 2000:
            print("Не вдалось згенерувати поле з шляхом за багато спроб. Спробуйте змінити p.")
            return
 
    print("\nЗгенероване поле (вирівняне):")
    print_board_numbered(grid, None)
 
    if not exists_path_bfs(grid):
        print("Шляху немає — завершую.")
        return
 
    print(f"Починаємо пошук найдовшого простого шляху (таймаут = {tlim} сек)...")
    best = longest_path_dfs(grid, time_limit=tlim, randomize=True)
 
    if not best:
        print("Не знайдено жодного шляху (неочікувано).")
        return
 
    print(f"Знайдений шлях довжиною {len(best)} (0 = старт).")
    print("\nКарта з пронумерованим шляхом:")
    print_board_numbered(grid, best)
 
    print("\nКроки шляху (1-based координати):")
    print([(r+1, c+1) for (r,c) in best])
 
if __name__ == "__main__":
    main()

aW1wb3J0IHJhbmRvbQppbXBvcnQgdGltZQppbXBvcnQgc3lzCiAKc3lzLnNldHJlY3Vyc2lvbmxpbWl0KDEwMDAwKQogCmRlZiBnZW5lcmF0ZV9maWVsZChOLCBNLCBwKToKICAgIGdyaWQgPSBbWzEgaWYgcmFuZG9tLnJhbmRvbSgpIDwgcCBlbHNlIDAgZm9yIF8gaW4gcmFuZ2UoTSldIGZvciBfIGluIHJhbmdlKE4pXQogICAgZ3JpZFtOLTFdWzBdID0gMCAgICMg0YHRgtCw0YDRgiAo0LvRltCy0LjQuSDQvdC40LbQvdGW0LkpCiAgICBncmlkWzBdW00tMV0gPSAwICAgIyDRhNGW0L3RltGIICjQv9GA0LDQstC40Lkg0LLQtdGA0YXQvdGW0LkpCiAgICByZXR1cm4gZ3JpZAogCmZyb20gY29sbGVjdGlvbnMgaW1wb3J0IGRlcXVlCmRlZiBleGlzdHNfcGF0aF9iZnMoZ3JpZCk6CiAgICBOLCBNID0gbGVuKGdyaWQpLCBsZW4oZ3JpZFswXSkKICAgIHN0YXJ0ID0gKE4tMSwwKQogICAgZ29hbCA9ICgwLCBNLTEpCiAgICBpZiBncmlkW3N0YXJ0WzBdXVtzdGFydFsxXV0gIT0gMCBvciBncmlkW2dvYWxbMF1dW2dvYWxbMV1dICE9IDA6CiAgICAgICAgcmV0dXJuIEZhbHNlCiAgICBxID0gZGVxdWUoW3N0YXJ0XSkKICAgIHZpcyA9IFtbRmFsc2VdKk0gZm9yIF8gaW4gcmFuZ2UoTildCiAgICB2aXNbc3RhcnRbMF1dW3N0YXJ0WzFdXSA9IFRydWUKICAgIGRpcnMgPSBbKDEsMCksKC0xLDApLCgwLDEpLCgwLC0xKV0KICAgIHdoaWxlIHE6CiAgICAgICAgcixjID0gcS5wb3BsZWZ0KCkKICAgICAgICBpZiAocixjKSA9PSBnb2FsOgogICAgICAgICAgICByZXR1cm4gVHJ1ZQogICAgICAgIGZvciBkcixkYyBpbiBkaXJzOgogICAgICAgICAgICBuciwgbmMgPSByK2RyLCBjK2RjCiAgICAgICAgICAgIGlmIDAgPD0gbnIgPCBOIGFuZCAwIDw9IG5jIDwgTSBhbmQgbm90IHZpc1tucl1bbmNdIGFuZCBncmlkW25yXVtuY10gPT0gMDoKICAgICAgICAgICAgICAgIHZpc1tucl1bbmNdID0gVHJ1ZQogICAgICAgICAgICAgICAgcS5hcHBlbmQoKG5yLG5jKSkKICAgIHJldHVybiBGYWxzZQogCmRlZiBsb25nZXN0X3BhdGhfZGZzKGdyaWQsIHRpbWVfbGltaXQ9MS41LCByYW5kb21pemU9VHJ1ZSk6CiAgICBOLCBNID0gbGVuKGdyaWQpLCBsZW4oZ3JpZFswXSkKICAgIHN0YXJ0ID0gKE4tMSwgMCkKICAgIGdvYWwgPSAoMCwgTS0xKQogICAgZGlycyA9IFsoMSwwKSwgKDAsMSksICgtMSwwKSwgKDAsLTEpXSAgCiAgICBiZXN0X3BhdGggPSBOb25lCiAgICBiZXN0X2xlbiA9IC0xCiAgICBzdGFydF90aW1lID0gdGltZS50aW1lKCkKICAgIG1heF9ub2RlcyA9IDEwKio2CiAgICBub2RlcyA9IDAKIAogICAgaW1wb3J0IHJhbmRvbSBhcyBfcm5kCiAKICAgIHZpc2l0ZWQgPSBbW0ZhbHNlXSpNIGZvciBfIGluIHJhbmdlKE4pXQogICAgcGF0aCA9IFtdCiAKICAgIGRlZiBkZnMocixjKToKICAgICAgICBub25sb2NhbCBiZXN0X2xlbiwgYmVzdF9wYXRoLCBub2RlcwogICAgICAgIGlmIHRpbWUudGltZSgpIC0gc3RhcnRfdGltZSA+IHRpbWVfbGltaXQ6CiAgICAgICAgICAgIHJldHVybgogICAgICAgIG5vZGVzICs9IDEKICAgICAgICBpZiBub2RlcyA+IG1heF9ub2RlczoKICAgICAgICAgICAgcmV0dXJuCiAKICAgICAgICBpZiAocixjKSA9PSBnb2FsOgogICAgICAgICAgICBpZiBsZW4ocGF0aCkgPiBiZXN0X2xlbjoKICAgICAgICAgICAgICAgIGJlc3RfbGVuID0gbGVuKHBhdGgpCiAgICAgICAgICAgICAgICBiZXN0X3BhdGggPSBwYXRoLmNvcHkoKQogICAgICAgICAgICByZXR1cm4KIAogICAgICAgIG5laWdocyA9IFtdCiAgICAgICAgZm9yIGRyLGRjIGluIGRpcnM6CiAgICAgICAgICAgIG5yLCBuYyA9IHIrZHIsIGMrZGMKICAgICAgICAgICAgaWYgMCA8PSBuciA8IE4gYW5kIDAgPD0gbmMgPCBNIGFuZCBub3QgdmlzaXRlZFtucl1bbmNdIGFuZCBncmlkW25yXVtuY10gPT0gMDoKICAgICAgICAgICAgICAgIGRpc3QgPSBhYnMobnIgLSBnb2FsWzBdKSArIGFicyhuYyAtIGdvYWxbMV0pCiAgICAgICAgICAgICAgICBuZWlnaHMuYXBwZW5kKChkaXN0LCBuciwgbmMpKQogICAgICAgIG5laWdocy5zb3J0KHJldmVyc2U9VHJ1ZSwga2V5PWxhbWJkYSB4OiB4WzBdKQogICAgICAgIGlmIHJhbmRvbWl6ZToKICAgICAgICAgICAgaSA9IDAKICAgICAgICAgICAgd2hpbGUgaSA8IGxlbihuZWlnaHMpOgogICAgICAgICAgICAgICAgaiA9IGkKICAgICAgICAgICAgICAgIHdoaWxlIGogPCBsZW4obmVpZ2hzKSBhbmQgbmVpZ2hzW2pdWzBdID09IG5laWdoc1tpXVswXToKICAgICAgICAgICAgICAgICAgICBqICs9IDEKICAgICAgICAgICAgICAgIGJsb2NrID0gbmVpZ2hzW2k6al0KICAgICAgICAgICAgICAgIF9ybmQuc2h1ZmZsZShibG9jaykKICAgICAgICAgICAgICAgIG5laWdoc1tpOmpdID0gYmxvY2sKICAgICAgICAgICAgICAgIGkgPSBqCiAKICAgICAgICBmb3IgXywgbnIsIG5jIGluIG5laWdoczoKICAgICAgICAgICAgaWYgdGltZS50aW1lKCkgLSBzdGFydF90aW1lID4gdGltZV9saW1pdDoKICAgICAgICAgICAgICAgIHJldHVybgogICAgICAgICAgICB2aXNpdGVkW25yXVtuY10gPSBUcnVlCiAgICAgICAgICAgIHBhdGguYXBwZW5kKChucixuYykpCiAgICAgICAgICAgIGRmcyhucixuYykKICAgICAgICAgICAgcGF0aC5wb3AoKQogICAgICAgICAgICB2aXNpdGVkW25yXVtuY10gPSBGYWxzZQogCiAgICBpZiBncmlkW3N0YXJ0WzBdXVtzdGFydFsxXV0gIT0gMCBvciBncmlkW2dvYWxbMF1dW2dvYWxbMV1dICE9IDA6CiAgICAgICAgcmV0dXJuIE5vbmUKIAogICAgdmlzaXRlZFtzdGFydFswXV1bc3RhcnRbMV1dID0gVHJ1ZQogICAgcGF0aC5hcHBlbmQoc3RhcnQpCiAgICBkZnMoc3RhcnRbMF0sIHN0YXJ0WzFdKQogICAgdmlzaXRlZFtzdGFydFswXV1bc3RhcnRbMV1dID0gRmFsc2UKICAgIHBhdGgucG9wKCkKIAogICAgcmV0dXJuIGJlc3RfcGF0aAogCiAKZGVmIHByaW50X2JvYXJkX251bWJlcmVkKGdyaWQsIHBhdGgpOgogICAgTiwgTSA9IGxlbihncmlkKSwgbGVuKGdyaWRbMF0pCiAgICBzdGVwID0ge30KICAgIGlmIHBhdGg6CiAgICAgICAgZm9yIGksIGNlbGwgaW4gZW51bWVyYXRlKHBhdGgpOgogICAgICAgICAgICBzdGVwW2NlbGxdID0gaQogCiAgICBtYXhfc3RlcCA9IG1heChzdGVwLnZhbHVlcygpKSBpZiBzdGVwIGVsc2UgMAogICAgd2lkdGggPSBtYXgoMywgbGVuKHN0cihtYXhfc3RlcCkpICsgMikKIAogICAgZGVmIGNlbGxfc3RyKHMpOgogICAgICAgIHJldHVybiBzdHIocykuY2VudGVyKHdpZHRoKQogCiAgICBwcmludCgpCiAgICBmb3IgciBpbiByYW5nZShOKToKICAgICAgICByb3dfY2VsbHMgPSBbXQogICAgICAgIGZvciBjIGluIHJhbmdlKE0pOgogICAgICAgICAgICBpZiAocixjKSBpbiBzdGVwOgogICAgICAgICAgICAgICAgcm93X2NlbGxzLmFwcGVuZChjZWxsX3N0cihzdGVwWyhyLGMpXSkpCiAgICAgICAgICAgIGVsaWYgZ3JpZFtyXVtjXSA9PSAxOgogICAgICAgICAgICAgICAgcm93X2NlbGxzLmFwcGVuZChjZWxsX3N0cigiIyIpKQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgcm93X2NlbGxzLmFwcGVuZChjZWxsX3N0cigiLiIpKQogICAgICAgIHByaW50KCIiLmpvaW4ocm93X2NlbGxzKSkKICAgIHByaW50KCkKIAogCmRlZiBtYWluKCk6CiAgICBwcmludCgiPT09INCf0L7Qu9GPINGWINC60LDQvNGW0L3QvdGPIOKAlCDQv9C+0YjRg9C6INC00L7QstCz0L7Qs9C+INC/0YDQvtGB0YLQvtCz0L4g0YjQu9GP0YXRgyIpCiAgICB0cnk6CiAgICAgICAgTiA9IGludChpbnB1dCgi0JLQstC10LTRltGC0Ywg0LrRltC70YzQutGW0YHRgtGMINGA0Y/QtNC60ZbQsiBOICgxLi4xMDApOiAiKS5zdHJpcCgpKQogICAgICAgIE0gPSBpbnQoaW5wdXQoItCS0LLQtdC00ZbRgtGMINC60ZbQu9GM0LrRltGB0YLRjCDRgdGC0L7QstC/0YbRltCyIE0gKDEuLjEwMCk6ICIpLnN0cmlwKCkpCiAgICBleGNlcHQgRXhjZXB0aW9uOgogICAgICAgIHByaW50KCLQndC10LrQvtGA0LXQutGC0L3RliBOINCw0LHQviBNLiIpCiAgICAgICAgcmV0dXJuCiAgICBpZiBub3QgKDEgPD0gTiA8PSAxMDAgYW5kIDEgPD0gTSA8PSAxMDApOgogICAgICAgIHByaW50KCJOINGWIE0g0L/QvtCy0LjQvdC90ZYg0LHRg9GC0Lgg0LLRltC0IDEg0LTQviAxMDAuIikKICAgICAgICByZXR1cm4KIAogICAgdHJ5OgogICAgICAgIHAgPSBmbG9hdChpbnB1dCgi0JnQvNC+0LLRltGA0L3RltGB0YLRjCDQutCw0LzQtdC90Y4g0LIg0LrQu9GW0YLQuNC90YbRliAoMC4uMSksINC90LDQv9GA0LjQutC70LDQtCAwLjI1OiAiKS5zdHJpcCgpKQogICAgICAgIGlmIG5vdCAoMC4wIDw9IHAgPD0gMS4wKToKICAgICAgICAgICAgcmFpc2UgVmFsdWVFcnJvcigpCiAgICBleGNlcHQgRXhjZXB0aW9uOgogICAgICAgIHByaW50KCLQndC10LrQvtGA0LXQutGC0L3QtSBwIOKAlCDQstC40LrQvtGA0LjRgdGC0L7QstGD0Y4gMC4yNSIpCiAgICAgICAgcCA9IDAuMjUKIAogICAgdHJ5OgogICAgICAgIHRsaW0gPSBmbG9hdChpbnB1dCgi0KfQsNGB0L7QstC40Lkg0LvRltC80ZbRgiDQv9C+0YjRg9C60YMg0LIg0YHQtdC60YPQvdC00LDRhSAo0L3QsNC/0YDQuNC60LvQsNC0IDEuNSk6ICIpLnN0cmlwKCkpCiAgICAgICAgaWYgdGxpbSA8PSAwOgogICAgICAgICAgICB0bGltID0gMS41CiAgICBleGNlcHQgRXhjZXB0aW9uOgogICAgICAgIHRsaW0gPSAxLjUKIAogICAgcmVnZW4gPSBpbnB1dCgi0K/QutGJ0L4g0L/QvtGC0YDRltCx0L3QviDigJQg0YDQtdCz0LXQvdC10YDRg9Cy0LDRgtC4INC/0L7Qu9C1INC/0L7QutC4INGW0YHQvdGD0ZQg0YjQu9GP0YU/ICjRgi/QvSkgW9GCXTogIikuc3RyaXAoKS5sb3dlcigpCiAgICByZWdlbl9mbGFnID0gKHJlZ2VuID09ICIiIG9yIHJlZ2VuID09ICLRgiIgb3IgcmVnZW4gPT0gInkiIG9yIHJlZ2VuID09ICJ5ZXMiKQogCiAgICBhdHRlbXB0cyA9IDAKICAgIHdoaWxlIFRydWU6CiAgICAgICAgYXR0ZW1wdHMgKz0gMQogICAgICAgIGdyaWQgPSBnZW5lcmF0ZV9maWVsZChOLCBNLCBwKQogICAgICAgIGlmIGV4aXN0c19wYXRoX2JmcyhncmlkKToKICAgICAgICAgICAgYnJlYWsKICAgICAgICBpZiBub3QgcmVnZW5fZmxhZzoKICAgICAgICAgICAgYnJlYWsKICAgICAgICBpZiBhdHRlbXB0cyA+IDIwMDA6CiAgICAgICAgICAgIHByaW50KCLQndC1INCy0LTQsNC70L7RgdGMINC30LPQtdC90LXRgNGD0LLQsNGC0Lgg0L/QvtC70LUg0Lcg0YjQu9GP0YXQvtC8INC30LAg0LHQsNCz0LDRgtC+INGB0L/RgNC+0LEuINCh0L/RgNC+0LHRg9C50YLQtSDQt9C80ZbQvdC40YLQuCBwLiIpCiAgICAgICAgICAgIHJldHVybgogCiAgICBwcmludCgiXG7Ql9Cz0LXQvdC10YDQvtCy0LDQvdC1INC/0L7Qu9C1ICjQstC40YDRltCy0L3Rj9C90LUpOiIpCiAgICBwcmludF9ib2FyZF9udW1iZXJlZChncmlkLCBOb25lKQogCiAgICBpZiBub3QgZXhpc3RzX3BhdGhfYmZzKGdyaWQpOgogICAgICAgIHByaW50KCLQqNC70Y/RhdGDINC90LXQvNCw0ZQg4oCUINC30LDQstC10YDRiNGD0Y4uIikKICAgICAgICByZXR1cm4KIAogICAgcHJpbnQoZiLQn9C+0YfQuNC90LDRlNC80L4g0L/QvtGI0YPQuiDQvdCw0LnQtNC+0LLRiNC+0LPQviDQv9GA0L7RgdGC0L7Qs9C+INGI0LvRj9GF0YMgKNGC0LDQudC80LDRg9GCID0ge3RsaW19INGB0LXQuikuLi4iKQogICAgYmVzdCA9IGxvbmdlc3RfcGF0aF9kZnMoZ3JpZCwgdGltZV9saW1pdD10bGltLCByYW5kb21pemU9VHJ1ZSkKIAogICAgaWYgbm90IGJlc3Q6CiAgICAgICAgcHJpbnQoItCd0LUg0LfQvdCw0LnQtNC10L3QviDQttC+0LTQvdC+0LPQviDRiNC70Y/RhdGDICjQvdC10L7Rh9GW0LrRg9Cy0LDQvdC+KS4iKQogICAgICAgIHJldHVybgogCiAgICBwcmludChmItCX0L3QsNC50LTQtdC90LjQuSDRiNC70Y/RhSDQtNC+0LLQttC40L3QvtGOIHtsZW4oYmVzdCl9ICgwID0g0YHRgtCw0YDRgikuIikKICAgIHByaW50KCJcbtCa0LDRgNGC0LAg0Lcg0L/RgNC+0L3Rg9C80LXRgNC+0LLQsNC90LjQvCDRiNC70Y/RhdC+0Lw6IikKICAgIHByaW50X2JvYXJkX251bWJlcmVkKGdyaWQsIGJlc3QpCiAKICAgIHByaW50KCJcbtCa0YDQvtC60Lgg0YjQu9GP0YXRgyAoMS1iYXNlZCDQutC+0L7RgNC00LjQvdCw0YLQuCk6IikKICAgIHByaW50KFsocisxLCBjKzEpIGZvciAocixjKSBpbiBiZXN0XSkKIAppZiBfX25hbWVfXyA9PSAiX19tYWluX18iOgogICAgbWFpbigp

MjUKMjUKMC4yNQoxLjUK0YI=

25
25
0.25
1.5
т