#include "testlib.h"
#include <vector>
#include <queue>

using namespace std;

// Directions for moving in 4 possible directions (up, down, left, right).
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

// Helper function to check if a cell (x, y) is inside the grid.
bool inBounds(int x, int y, int n, int m) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

// Prim’s algorithm for maze generation.
void generateMaze(vector<vector<char>>& grid, int n, int m) {
    vector<pair<int, int>> walls;

    // Start carving from (1, 1)
    grid[1][1] = '.';
    for (int i = 0; i < 4; i++) {
        int nx = 1 + dx[i], ny = 1 + dy[i];
        if (inBounds(nx, ny, n, m))
            walls.push_back({nx, ny});
    }

    // Process walls until there are none left
    while (!walls.empty()) {
        int idx = rnd.next(0, (int)walls.size() - 1);
        auto [x, y] = walls[idx];
        walls.erase(walls.begin() + idx);

        int count = 0;
        int px = -1, py = -1;

        // Check the number of adjacent cells that are paths ('.')
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (inBounds(nx, ny, n, m) && grid[nx][ny] == '.') {
                count++;
                px = nx;
                py = ny;
            }
        }

        // If only one adjacent cell is a path, we can safely carve this cell
        if (count == 1) {
            grid[x][y] = '.';

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (inBounds(nx, ny, n, m) && grid[nx][ny] == '#')
                    walls.push_back({nx, ny});
            }
        }
    }
}

int main(int argc, char* argv[]) {
    // Initialize testlib for generating random tests.
    registerGen(argc, argv, 1);
    
    std::cout << 1 << std::endl;

    int n = atoi(argv[1]);
    int m = atoi(argv[2]);
    // Define grid dimensions
    // int n = rnd.next(5, 25); // Use a larger range for maze-like grids
    // int m = rnd.next(5, 25);

    // Ensure dimensions are odd for better maze generation.
    if (n % 2 == 0) n++;
    if (m % 2 == 0) m++;

    // Initialize the grid with walls.
    vector<vector<char>> grid(n, vector<char>(m, '#'));

    // Generate a maze using Prim's algorithm
    generateMaze(grid, n, m);

    // Randomly place start ('s') and finish ('f') cells in open spaces
    int sx = 1, sy = 1; // Start at the beginning of the maze
    int fx = n - 2, fy = m - 2; // Finish near the opposite corner

    grid[sx][sy] = 's';
    grid[fx][fy] = 'f';

    // Output the grid
    println(n, m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            printf("%c", grid[i][j]);
        }
        printf("\n");
    }

    return 0;
}