#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <list> using namespace std; #define M 2002*2 typedef struct Tree { int data; struct Tree *lson,*rson; } Tnode,*ListTree; int cnt; ListTree a,b; int n,m; int* init(char *str,int &s) { int* strn=(int *)malloc(sizeof(int)*M); int len=strlen(str); int tmp=0; int k=0; str[len]=' '; len++; for(int i=0; i<len; i++) { if(str[i]==' ') { strn[k++]=tmp; //cout<<tmp<<' '; tmp=0; } else { tmp=tmp*10+str[i]-'0'; } } s=k; return strn; } ListTree built(int *arr) { ListTree list; if(arr[cnt++]==0) list=NULL; else { list=(ListTree)malloc(sizeof(Tnode)); list->data=arr[cnt-1]; if(n==arr[cnt-1]) a=list; if(m==arr[cnt-1]) b=list; list->lson=built(arr); list->rson=built(arr); } return list; } bool getPath(ListTree root,ListTree node,list<ListTree>&path) { if(root==NULL) return false; if(root==node) return true; path.push_back(root); bool found=false; found=getPath(root->lson,node,path); if(!found) { found=getPath(root->rson,node,path); } if(!found) path.pop_back(); return found; } ListTree getComm(list<ListTree>path1,list<ListTree>path2) { list<ListTree>::const_iterator it1=path1.begin(); list<ListTree>::const_iterator it2=path2.begin(); ListTree ans=NULL; while(it1!=path1.end()&&it2!=path2.end()) { if(*it1==*it2) ans=*it1; it1++; it2++; } return ans; } ListTree getLastNode(ListTree root,ListTree ra,ListTree rb) { if(root==NULL||ra==NULL ||rb==NULL) return NULL; list<ListTree>path1,path2; path1.clear(); path2.clear(); bool f1=getPath(root,ra,path1); bool f2=getPath(root,rb,path2); if(f1&&f2) { return getComm(path1,path2); } else return NULL ; } void output(ListTree root) { if(root==NULL) return ; cout<<root->data<<" "; output(root->lson); output(root->rson); return ; } int main() { int cas; scanf("%d",&cas); getchar(); while(cas--) { char *str=(char *)malloc(sizeof(char)*M); gets(str); int k; scanf("%d %d",&n,&m); int *p=init(str,k); cnt=0; ListTree mytree=built(p); ListTree ans=getLastNode(mytree,a,b); if(ans!=NULL) printf("%d\n",ans->data); else printf("My God\n"); getchar(); } return 0; }