描述

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。

输入格式

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (\le 10≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。最后L行，每行给出N个插入的元素，属于L个需要检查的序列。

简单起见，我们保证每个插入序列都是1到NN的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。

输出格式

对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。

样例

输入

4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0

输出

Yes
No
No

c++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <stdio.h>
#include <stack>
using namespace std;
#define md 1000000007;
struct  tree
{
	tree * lson;
	tree * rson;
	int value;
};
tree * head;
tree * exa;
void build( tree * tmp,int cc){
    if(tmp->value>cc){
        if(tmp->lson!=NULL)build(tmp->lson,cc);
        else{
            tree * tt=new tree();tt->lson=NULL;tt->rson=NULL;
            tt->value=cc;
            tmp->lson=tt;
        }
    }
    else if(tmp->value<cc){
        if(tmp->rson!=NULL)build(tmp->rson,cc);
        else{
            tree * tt=new tree();tt->lson=NULL;tt->rson=NULL;
            tt->value=cc;
            tmp->rson=tt;
        }
    }
}
void preorder(tree * tt){
	cout<<tt->value<<" ";
	if(tt->lson!=NULL)preorder(tt->lson);
	if(tt->rson!=NULL)preorder(tt->rson);
}
void midorder(tree * tt){
	if(tt->lson!=NULL)midorder(tt->lson);
	cout<<tt->value<<" ";
	if(tt->rson!=NULL)midorder(tt->rson);
}
void aftorder(tree * tt){
	if(tt->lson!=NULL)aftorder(tt->lson);
	if(tt->rson!=NULL)aftorder(tt->rson);
	cout<<tt->value<<" ";
}
bool treecmp(tree * a,tree * b){
   // cout<<"cmpareing the value of a // b   "<<a->value<<"  "<<b->value<<endl;
    if(a==NULL&&b==NULL)return 1;
    else if(a!=NULL && b!= NULL && a->value == b->value) {
        if(treecmp(a->lson,b->lson)&&treecmp(a->rson,b->rson))return 1;
        else return 0;
    } else return 0;
}
int main()
{
	int n;cin>>n;
    while(n!=0){
        int l,tt,tmp;cin>>l;
        cin>>tt;
        head=new tree();head->lson=NULL;head->rson=NULL;head->value=tt;
        for(int i=1;i<n;i++){
            cin>>tt;
            build(head,tt);
        }
         /* cout<<"head de pre mid aft:"<<endl;
            preorder(head);puts("");
            midorder(head);puts("");
            aftorder(head);puts("");
            puts("-------------------");*/
        while(l--){
            exa=new tree();
            cin>>tt;
            exa->lson=NULL;exa->rson=NULL;exa->value=tt;
            for(int i=1;i<n;i++){
                cin>>tt;
                build(exa,tt);
            }
            if(treecmp(head,exa))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
            /*cout<<"exa de pre mid aft:"<<endl;
            preorder(exa);puts("");
            midorder(exa);puts("");
            aftorder(exa);puts("");
            puts("-------------------");*/
        }
        cin>>n;
    }
	return 0;
}