#include<bits/stdc++.h>
#define ll long long
#define N ((int)6e4 + 5)
#define MOD ((int)1e9 + 7)
#define MAX ((int)1e9 + 7)
#define MAXL ((ll)1e18 + 7)
#define MAXP ((int)1e3 + 7)
#define thr 1e-8
#define pi acos(-1)  /// pi = acos ( -1 )
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
#define endl "\n"

using namespace std;

/// coloring

/// coloring type 1

bool dfs(int n, int c)
{
    if(vis[n] == 1){
        if(col[n] == c) return true;
        else return false;
    }

    vis[n] = 1;
    col[n] = c;
    bool ans = true;
    for(int a:edge[n]){
        ans &= dfs(a , !c);
    }
    return ans;
}

vector < pair < int , int > > edge[N];

vector < int > comp[2];

/// coloring type 2

bool dfs(int n , int c)
{
    if(vis[n] == 1){
        if(col[n] == c) return true;
        else return false;
    }

    vis[n] = 1;
    col[n] = c;
    comp[c].push_back(n);

    bool ans = true;

    for(auto p:edge[n]){
        int a = p.first , type = p.second;
        ans &= dfs(a , c ^ type);
    }
    return ans;
}



/// problem: https://www.spoj.com/problems/SERGRID/

int dxx[] = {0,0,1,-1};
int dyy[] = {1,-1,0,0};

bool IsValid(int  row , int col)
{
    if(min(row , col) < 0 || row >= n || col >= m || dis[row][col] != -1) return 0;
    return 1;
}

void bfs(int row , int col)
{
    memset(dis,-1,sizeof dis);
    queue <pair < int , int > > que;
    que.push({row , col});
    dis[row][col] = 0;

    while(!que.empty()){
        row = que.front().first, col = que.front().second;
        que.pop();
        int digit = str[row][col] - '0';
        for(int i = 0 ; i < 4 ; i++){
            int x  = row + dxx[i]*digit , y = col + dyy[i]*digit;
            if(IsValid(x,y)){
                dis[x][y] = dis[row][col] + 1;
                que.push({x,y});
            }
        }
    }

}