/*
题意：
1、给出两个首地址，N个字符，然后给出地址，字符，下一个地址
2、找出两个字符的公共后缀，输出地址，没有则输出-1
解题：
1、直接使用静态链表，不超过10的5次，定义一个flag
2、遍历第一条链表，将经过的所有节点的flag值赋为1
枚举第二条链表，如果第一个flag值为1，就说明有，则说明第一条链表中出现过的结果即为两条链表的第一个公用节点
learn&&wrong：
1、使用%05d格式输出地址，可以使不足5位补足高位为0
2、使用%c可以读入空格，因为在输入地址、数据及后继节点地址时，格式不能写成%d%c%d，必须在中间加空格
3、for遍历静态链表需要学习一下
4、这题的结构体里没有address，而其他题目有，主要是，他不需要输出下一个的address
*/
include <iostream>
include <cstdio>
using namespace std;
const int maxn = 100010;
struct NODE{
char data; //数据域
int next; //指针域
bool flag; //判断第一个节点是否在链表中出现
}node[maxn];
int main()
{
for(int i = 0;i < maxn;i++){
node[i].flag = false;
}
int s1, s2, n; //将s1和s2分别代表两条链表的首地址
scanf("%d%d%d",&s1,&s2,&n);
int address,next; //节点地址以及后继节点地址
char data; //数据
for(int i = 0;i < n;i++){
scanf("%d %c %d", &address,&data,&next);
node[address].data = data;
node[address].next = next;
}
int p;
for(p = s1;p != -1;p = node[p].next){
node[p].flag = true; //枚举第一条链表的所有结点，令其出现次数为1
}
for(p = s2;p != -1;p = node[p].next){
if(node[p].flag == true) break;
}
if(p != -1){ //如果第二条链表还没有到达结尾，则说明找到了公用节点
printf("%05d\n", p);
}else{
printf("-1\n");
}
return 0;
}
