#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <sstream>
#include <stack>
#include <map>
#include <ctime>
#include <array>
#include <set>
#include <list>
using namespace std;
//边的定义
template<class TypeOfEdge>
struct Edge_pair
{
	int point = 0;
	TypeOfEdge length = 0;
	//=================
};
//顶点的定义
template<class TypeOfVer, class TypeOfEdge>
struct verNode
{
	TypeOfVer ver_data;
	int V_E,V_L;
	list<Edge_pair<TypeOfEdge> > group;
	//构造函数，默认会讲头指针设为空.
	verNode()
	{
		group.clear();
		//ver_data = 0;
	}
	//取得结点值（顶点） 估计是为了安全吧？？？
	TypeOfVer getVer()
	{
		return ver_data;
	}
	//取得对应的边表
	list<Edge_pair<TypeOfEdge> > getHead()
	{
		return group;
	}
	//设置结点值（顶点集） 估计是为了安全吧？？？
	void setdata(TypeOfVer value)
	{
		ver_data = value;
		return;
	}
	//=====================================================

	void creat_Point(int new_point, TypeOfEdge new_length)
	{
		Edge_pair<TypeOfEdge> Next_p;
		Next_p.point = new_point;
		Next_p.length = new_length;
		group.insert(group.begin(), Next_p);
		return;
	}
	//删除指定位置顶点
	void del_Point(int n)
	{

		return;
	}
};

template <class TypeOfVer, class TypeOfEdge>//顶点元素类型，边权值类型
class adjlist_graph {
private:
	int Vers;//顶点数
	int Edges;//边数
	vector<verNode<TypeOfVer, TypeOfEdge> >ver;//顶点存储
	string GraphKind;//图的种类标志
	bool have_dir = false, have_w = false;//图类型参数


public:
	//一个空的构造函数
	adjlist_graph()
	{
		Edges = 0;
		Vers = 0;
	}
	//假的析构函数
	~adjlist_graph()
	{
		;//你电脑内存就640K吗？
	}
	//判断图空否
	bool GraphisEmpty()
	{
		return Vers == 0;
	}
	//获取图的类型
	string GetGraphKind()
	{
		return GraphKind;
	}
	//取得当前顶点数
	int GetVerNum()
	{
		return Vers;
	}
	//取得当前边数
	int GetEdgeNum()
	{
		return Edges;
	}
	//自动建立临接表
	bool Auto_build(void)
	{
		//DG（有向图）, DN（有向网）, UDG（无向图）, UDN（无向网）
		/*第一行：图的类型  DN UDN
		第二行：结点数
		第三行：结点集
		第四行：无边标记
		第五行：边数
		第六行：边集
		第七行：权集*/

		/*第一行：图的类型  DG UDG
		第二行：结点数
		第三行：结点集
		第四行：边数
		第五行：边集*/
		cin >> GraphKind;//图的类型
		cin >> Vers;//结点数
		ver.resize(Vers);//开辟节点空间
		for (int i = 0; i < Vers; i++)//结点集
		{
			TypeOfVer now;
			cin >> now;
			ver[i].setdata(now);
		}


		cin >> Edges;//边数
		vector<int> x_p, y_p, w_p;
		for (int i = 0; i < Edges; i++)
		{
			int c_x, c_y;
			cin >> c_x >> c_y;
			x_p.push_back(c_x);
			y_p.push_back(c_y);
		}
		//图的类型识别

		if (GraphKind == "DG")//DG（有向图）
			have_dir = true, have_w = false;
		if (GraphKind == "DN")//DN（有向网）
			have_dir = true, have_w = true;
		if (GraphKind == "UDG")//UDG（无向图）
			have_dir = false, have_w = false;
		if (GraphKind == "UDN")//UDN（无向网）
			have_dir = false, have_w = true;

		if (have_w)
			for (int i = 0; i < Edges; i++)
			{
				int c_w;
				cin >> c_w;
				w_p.push_back(c_w);
			}


		for (int i = 0; i < Edges; i++)
		{
			if (have_dir)
				if (have_w)
					ver[x_p[i]].creat_Point(y_p[i], w_p[i]);
				else
					ver[x_p[i]].creat_Point(y_p[i], 0);
			else
				if (have_w)
					ver[x_p[i]].creat_Point(y_p[i], w_p[i]), ver[y_p[i]].creat_Point(x_p[i], w_p[i]);
				else
					ver[x_p[i]].creat_Point(y_p[i], 0), ver[y_p[i]].creat_Point(x_p[i], 0);
		}
		return 1;
	}
	//取得G顶点的组
	vector<TypeOfVer> GetVer(void)
	{
		vector<TypeOfVer> head_group;
		for (int i = 0; i < Vers; i++)
		{
			head_group.push_back(ver[i].getVer());
		}
		return head_group;
	}
	//输出邻接表
	bool Print_photo()
	{
		int i;
		for (i = 0; i < Vers; i++)
		{
			cout << ver[i].getVer();
			if (ver[i].group.size() != 0)
				cout << "->";
			else
			{
				cout << endl;
				continue;
			}
			vector<Edge_pair<TypeOfEdge> > out_lis;
			out_lis.clear();
			for (auto j = ver[i].group.begin(); j != ver[i].group.end(); j++)
			{
				out_lis.push_back(*j);
			}
			int j;
			for (j = 0; j < out_lis.size() - 1; j++)
				if (have_w)
					cout << out_lis[j].point << "(" << out_lis[j].length << ")" << "->";
				else
					cout << out_lis[j].point << "->";
			if (have_w)
				cout << out_lis[j].point << "(" << out_lis[j].length << ")" << endl;
			else
				cout << out_lis[j].point << endl;
		}
		return 1;
	}
	//返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1
	int GetFirst_AdjVex(int u)
	{
		if(ver[u].group.empty())
			return -1;
		return ver[u].group.begin()->point;
	}
	//返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。若顶点在G中没有邻接顶点，则返回false
	int GetNext_AdjVex(int u, int v)
	{
		if (ver[u].group.size() == 1)
			return -1;
		for (auto i = ver[u].group.begin(); i != ver[u].group.end(); i++)
		{
			if (i->point == v)
			{
				if ((++i) == ver[u].group.end())
					return -1;
				return i->point;
			}
		}
		return -1;
	}

	//是否存在边
	bool look_Edge(int u, int v)
	{
		if (!(0 <= u && u < Vers))
			return false;
		if (!(0 <= v && v < Vers))
			return false;
		if (u == v)
			return false;
		for (auto i = ver[u].group.begin(); i != ver[u].group.end(); i++)
		{
			if (i->point == v)
				return true;
		}
		for (auto i = ver[v].group.begin(); i != ver[v].group.end(); i++)
		{
			if (i->point == u)
				return true;
		}
		return false;
	}
	//两个顶点之间的边的权值 失败返回-1
	int Get_legthOfEdge(int u, int v)
	{
		if (!have_w)
			return -1;
		if (!(0 <= u && u < Vers))
			return -1;
		if (!(0 <= v && v < Vers))
			return -1;
		if (u == v)
			return -1;
		for (auto i = ver[u].group.begin(); i != ver[u].group.end(); i++)
		{
			if (i->point == v)
				return i->length;
		}
		return -1;
	}
	//获取一个顶点的入度
	int Search_enterDegree(int p)
	{
		if (!(0 <= p && p < Vers))
			return -1;
		if (!have_dir)//is 无向图
			return ver[p].group.size();
		int cnt = 0;
		for (int i = 0; i < Vers; i++)
		{
			if(i!=p)
				for (auto j = ver[i].group.begin(); j != ver[i].group.end(); j++)
				{
					if (j->point == p)
						cnt++;
				}
		}
		//cnt += ver[p].group.size();
		return cnt;
	}
	//拓扑排序并判断有无回路 0 有 1 无
	vector<int> sort_list;//the way of sort
	bool TopologicalSort(void)
	{
		if (Edges == 0)
			return 0;
		int i, j;
		//将各个顶点的入度存在indegree
		vector<int> indegree;
		indegree.clear();
		//------
		for (i = 0; i < Vers; i++)
			indegree.push_back(Search_enterDegree(i));
		//------
		//入度为0，进栈。
		queue<int> S;
		//------
		for (i = 0; i < indegree.size(); i++)
			if (indegree[i] == 0)
				S.push(i);
		//------

		//BFS
		while (!S.empty())
		{
			int now;
			now = S.front();
			S.pop();
			sort_list.push_back(now);
			int next_p;
			next_p = GetFirst_AdjVex(now);//获取now的第一个相邻的点
			while (next_p != -1)
			{
				--indegree[next_p];
				if (indegree[next_p] == 0)
					S.push(next_p);
				/*if (indegree[next_p] == -1)
					S.push(next_p);*/
				next_p = GetNext_AdjVex(now, next_p);
			}
		}
		if (sort_list.size() == 0)
			return 0;
		if (sort_list.size() < Vers)
			return 0;
		return 1;
	}
	///==============
	//get the V_E and V_L;
    bool get_VeAndVl(void)///获取最早和最迟发生
    {
        int i,j,k;
        if(!TopologicalSort())///判断是否合法
            return false;
        //=======================最早发生
        for(i=0;i<Vers;i++)
            ver[i].V_E=0;
        for(i=0;i<Vers;i++)
        {
            int now=sort_list[i];
            int next_p;
			next_p = GetFirst_AdjVex(now);
            while (next_p != -1)
			{
			    ///获取一个最大值
				ver[next_p].V_E=max(ver[next_p].V_E,ver[now].V_E+Get_legthOfEdge(now,next_p));
				next_p = GetNext_AdjVex(now, next_p);
			}
        }
        ///=============最迟发生
        for(i=0;i<Vers;i++)
            ver[i].V_L=ver[Vers-1].V_E;
        //---
        for(i=Vers-1;i>=0;i--)
        {
            int now=sort_list[i];
            int next_p;
			next_p = GetFirst_AdjVex(now);
            while (next_p != -1)
			{
			    ///获取一个最大值
				ver[now].V_L=min(ver[now].V_L,ver[next_p].V_L-Get_legthOfEdge(now,next_p));
				//-----
				next_p = GetNext_AdjVex(now, next_p);
			}
        }
        ///out put=======================
        for(i=0;i<Vers;i++)
            cout<<ver[i].ver_data<<"\t"<<ver[i].V_E<<"\t"<<ver[i].V_L<<endl;
        return true;
    }
    struct pairOf_Edge{
    int x,y;
    int E,L;
    };
    vector<pairOf_Edge> open_way;
    bool get_EandL(void)///获取最早和最迟发生
    {
        int i;
        for(i=0;i<Vers;i++)
        {
            int next_p;
			next_p = GetFirst_AdjVex(i);
            while (next_p != -1)
			{
			    ///获取一个最大值
			    pairOf_Edge the_new;
			    the_new.x=i;
			    the_new.y=next_p;
                the_new.E=ver[i].V_E;
                the_new.L=ver[next_p].V_L-Get_legthOfEdge(i,next_p);
				open_way.push_back(the_new);///存储起来
				//-----
				next_p = GetNext_AdjVex(i, next_p);
			}
        }
        for(i=0;i<open_way.size();i++)
        {
            cout<<"<"<<ver[open_way[i].x].ver_data<<",";
            cout<<ver[open_way[i].y].ver_data<<">\t";
            cout<<open_way[i].E<<"\t"<<open_way[i].L<<endl;
        }
        cout<<endl;
        vector<int> same_list;//相同的点集合
        for(i=0;i<Vers;i++)
        {
            if(ver[i].V_E==ver[i].V_L)
                same_list.push_back(i);
        }
        if(same_list.size()>1)
            for(i=0;i<same_list.size()-1;i++)
            {
                cout<<"("<<ver[same_list[i]].ver_data<<",";
                cout<<ver[same_list[i+1]].ver_data<<")";
                if(i!=same_list.size()-2)
                    cout<<"->";
            }
        cout<<endl;
        return true;
    }
};


int main()
{
	int i;
	adjlist_graph<string, int> a;
	a.Auto_build();/*
	int u, v;
	cin >> u >> v;*/
	/*int p;
	cin >> p;*/
	//cout << a.GetGraphKind() << endl;
	vector <string> ans;
	ans = a.GetVer();
	for (i = 0; i < ans.size() - 1; i++)
		cout << ans[i] << " ";
	cout << ans[i] << endl;
	//cout << endl;
	//cout << a.GetVerNum() << endl;
	//cout << a.GetEdgeNum() << endl;
	a.Print_photo();

	cout << endl;
	if (a.get_VeAndVl())
    {
        cout<<endl;
        a.get_EandL();
    }
	else
		cout << "fuck you!The input wrong!" << endl;

	return 0;
}