The Eight Puzzle, among other sliding-tile puzzles, is one of the famous problems in artificial intelligence. Along with chess, tic-tac-toe and backgammon, it has been used to study search algorithms.

The Eight Puzzle can be generalized into an M × N Puzzle where at least one of M and N is odd. The puzzle is constructed with MN − 1 sliding tiles with each a number from 1 to MN − 1 on it packed into a M by N frame with one tile missing. For example, with M = 4 and N = 3, a puzzle may look like:

Let's call missing tile 0. The only legal operation is to exchange 0 and the tile with which it shares an edge. The goal of the puzzle is to find a sequence of legal operations that makes it look like:

The following steps solve the puzzle given above.

Given an M × N puzzle, you are to determine whether it can be solved.

The input consists of multiple test cases. Each test case starts with a line containing M and N (2 ≤ M, N ≤ 999). This line is followed by M lines containing N numbers each describing an M × N puzzle.

The input ends with a pair of zeroes which should not be processed.

Output one line for each test case containing a single word YES if the puzzle can be solved and NO otherwise.

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <string>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#define inf 2e9

#define met(a,b) memset(a,b,sizeof a)

typedef long long ll;

using namespace std;

const int N = *+;

const int M = 4e5+;

int n,m,tot=,cnt=;

int head[N],ans[N];

int tree[N];

int a[N];

void add(int k,int num) {

    while(k<=*-) {

        tree[k]+=num;

        k+=k&(-k);

    }

}

int Sum(int k) {

    int sum=;

    while(k>) {

        sum+=tree[k];

        k-=k&(-k);

    }

    return sum;

}

int main() {

    while(scanf("%d%d",&n,&m),n||m) {

        int x,y,t,s=,nu=;

        for(int i=; i<=n; i++)

            for(int j=; j<=m; j++) {

                scanf("%d",&t);

                if(t==)

                    x=i,y=j;

                else

                    a[nu++]=t;

            }

       met(tree,);

        for(int i=nu-; i>=; i--) {

            s+=Sum(a[i]-);

            add(a[i],);

        }

        if(m&)

            if(s&)puts("NO");

            else   puts("YES");

        else if(((n-x)^s)&) puts("NO");

        else            puts("YES");

    }

    return ;

}