To search a key in a binary search tree, we start from the root and move all the way down, choosing branches according to the comparison results of the keys. The searching path corresponds to a sequence of keys. For example, following {1, 4, 2, 3} we can find 3 from a binary search tree with 1 as its root. But {2, 4, 1, 3} is not such a path since 1 is in the right subtree of the root 2, which breaks the rule for a binary search tree. Now given a sequence of keys, you are supposed to tell whether or not it indeed correspnds to a searching path in a binary search tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N and M (<=100) which are the total number of sequences, and the size of each sequence, respectively. Then N lines follow, each gives a sequence of keys. It is assumed that the keys are numbered from 1 to M.

Output Specification:

For each sequence, print in a line "YES" if the sequence does correspnd to a searching path in a binary search tree, or "NO" if not.

Sample Input:

3 4

1 4 2 3

2 4 1 3

3 2 4 1

Sample Output:

YES

NO

NO

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<queue>

 #include<vector>

 using namespace std;

 struct node{

     int v;

     node *l,*r;

     node(){

         l=r=NULL;

     }

 };

 int main(){

     //freopen("D:\\INPUT.txt","r",stdin);

     int n,m;

     scanf("%d %d",&n,&m);

     while(n--){

         queue<int> q;

         int i,num;

         node *p,*pp,*h=NULL;

         for(i=;i<m;i++){

             scanf("%d",&num);

             q.push(num);

         }

         h=new node();

         h->v=q.front();

         q.pop();

         for(i=;i<m;i++){

             num=q.front();

             q.pop();

             p=h;

             while(p){

                 pp=p;//pp point to the father of p

                 if(num>p->v&&p->l==NULL){

                     p=p->r;

                 }

                 else{

                     if(num<p->v&&p->r==NULL){

                         p=p->l;

                     }

                     else

                         break;//防止元素相等

                 }

             }

             if(p==NULL){

                 p=new node();

                 p->v=num;

                 if(num>pp->v){

                     pp->r=p;

                 }

                 else{

                     pp->l=p;

                 }

             }

             else{

                 break;

             }

         }

         if(i==m){

             printf("YES\n");

         }

         else{

             printf("NO\n");

         }

     }

     return ;

 }

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<queue>

 #include<vector>

 using namespace std;

 struct node{

     int v;

     node *l,*r;

     node(){

         l=r=NULL;

     }

 };

 int main(){

     //freopen("D:\\INPUT.txt","r",stdin);

     int n,m;

     scanf("%d %d",&n,&m);

     while(n--){

         queue<int> q;

         int i,num,wantfind;

         node *p,*pp,*h;

         for(i=;i<m;i++){

             scanf("%d",&num);

             q.push(num);

         }

         wantfind=num;  //最后一个

         h=new node();

         h->v=q.front();

         q.pop();

         for(i=;i<m;i++){ //建树

             num=q.front();

             q.pop();

             p=h;

             while(p){

                 pp=p;//pp point to the father of p

                 if(num>p->v){

                     p=p->r;

                 }

                 else{

                     p=p->l;

                 }

             }

             p=new node();

             p->v=num;

             if(num>pp->v){

                 pp->r=p;

             }

             else{

                 pp->l=p;

             }

         }

         int count=;

         p=h;

         while(p){

             if(wantfind>p->v){

                 p=p->r;

             }

             else{

                 p=p->l;

             }

             count++;

         }

         if(count==m){

             printf("YES\n");

         }

         else{

             printf("NO\n");

         }

     }

     return ;

 }