#include <iostream>
#include <bits/stdc++.h>
using namespace std;
class DSU
{
public :
	int n;
	vector<int> sz;
	vector<int> parent;
	DSU (int num)
	{
		n= num;
		sz.resize(num+1,1);
		parent.resize(num+1,1);
		for(int i=0;i<=num;i++)
		{
			parent[i]=i;
		}
	}
	
	int findParent (int x)
	{
		if(x==parent[x])
		return x;
		else
		{
			return parent[x]= findParent(parent[x]);
		}
	}
	void unite(int x,int y)
	{
		int parentX = findParent(x);
		int parentY = findParent(y);
		if(sz[parentX] > sz [parentY])
		{
			parent[parentY]= parentX;
			sz[parentX] = sz[parentX] + sz[parentY];
		}
		else
		{
			parent[parentX]= parentY;
			sz[parentY] = sz[parentY] + sz[parentX];
		}
	}
};

int earliestConnectedTimestamp(vector<string> riders,  vector<string> logs)

{
	int components = riders.size();
	long long int timestamp;
	string person1,person2,relation;
	DSU dsu(components);
	unordered_map <string,int> usertoID;
	int id=0;
	for(int i=0;i<riders.size();i++)
	{
		usertoID.insert({riders[i],++id});
	}
	for(auto it : logs)
	{
		stringstream ss(it);
		ss>>timestamp>>person1>>relation>>person2;
		if(dsu.findParent(usertoID[person1])!=dsu.findParent(usertoID[person2]))
		{
			dsu.unite(usertoID[person1],usertoID[person2]);
			components--;
		}
		if(components==1)
		{
			return timestamp;
		}
	}
	return 0;
}

int main() {
	// your code goes here
	vector<string> riders = {
        "Alice",
        "Bob",
        "Charlie",
        "Dan",
        "Eve"
    };

    vector<string> logs = {
        "1670000001 Alice shared-ride-with Bob",
        "1670000042 Charlie shared-ride-with Dan",
        "1670000450 Bob shared-ride-with Charlie",
        "1670000501 Alice shared-ride-with Eve",
        "1670000621 Bob shared-ride-with Dan"
    };

    cout << earliestConnectedTimestamp(riders, logs) << endl;

    return 0;
}