1991

#include <iostream>
#include <vector>

using namespace std;

// 0 : 해당자리가 비어있음을 의미
int lc[26];
int rc[26];

void preorder(int cur){

  if(cur == -1)  return;

  cout << char(cur+'A');
  preorder(lc[cur]);
  preorder(rc[cur]);
}

void inorder(int cur){

  if(cur == -1)  return;

  inorder(lc[cur]);
  cout << char(cur+'A');
  inorder(rc[cur]);

}

void postorder(int cur){

  if(cur == -1)  return;

  postorder(lc[cur]);
  postorder(rc[cur]);
  cout << char(cur+'A');
}

int main() {

    fill(lc, lc+26, -1);
    fill(rc, rc+26, -1);

    int N;

    cin>>N;

    for(int i=0; i<N; i++){
      
      char c, l, r;

      cin>>c>>l>>r;
      if(l != '.')  lc[c-'A'] = l-'A';
      if(r != '.')  rc[c-'A'] = r-'A';

    }

    for(int i=0; i< 26; i++)
      cout<<lc[i]<<" ";

    preorder(0); cout<<'\n';
    inorder(0); cout<<'\n';
    postorder(0);
}

/*

ASCII코드표
A : 65
B : 66
...

*/