import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.lang.Math;
import java.util.Collections;
class point {
int index=-2;
String name;
int time;
int color=0; //1-cиний 2-красный
int IsBlue=0;
int mark=0;
int cap;
int dfs1=0;//нужна как флаг
int IsParent=1;
int distance=0;
ArrayList<point> list = new ArrayList<>();
ArrayList<point> way=new ArrayList<>();
}
class PriorityQueue{
int count;
point[] heap;
PriorityQueue(int n){
int i;
this.heap = new point[n];
for(i = 0; i < n; i++){
this.heap[i] = new point();
}
this.count = 0;
}
public void insert(point u){
int i = this.count++;
point temp;
this.heap[i] = u;
while (i > 0 && this.heap[(i-1)/2].distance > this.heap[i].distance){
temp = this.heap[(i-1)/2];
this.heap[(i-1)/2] = this.heap[i];
this.heap[i] = temp;
this.heap[i].index=i;
i = (i-1)/2;
}
this.heap[i].index=i;
}
public point ExtractMax(){
point temp;
temp = this.heap[0];
this.count--;
if(this.count > 0){
this.heap[0] = this.heap[this.count];
this.heap[0].index=0;
heapify(this.heap, 0);
}
return temp;
}
public void heapify(point[] heap, int i){
int l, r, j;
point temp;
for(;;){
l = 2*i+1;
r = l+1;
j = i;
if(l < this.count && (heap[l].distance < heap[j].distance)) j = l;
if(r < this.count && (heap[r].distance < heap[j].distance)) j = r;
if(i == j) break;
temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
this.heap[i].index=i;
this.heap[j].index=j;
i = j;
}
}
public void increaseKey(point x, int y){
int i = x.index;
point temp;
x.distance=y;
while(i > 0 && this.heap[(i-1)/2].distance > y){
temp = this.heap[(i-1)/2];
this.heap[(i-1)/2] = this.heap[i];
this.heap[i] = temp;
this.heap[i].index=i;
i = (i-1)/2;
}
x.index=i;
}
}
public class Cpm {
public static void main(String[] arg) {
Scanner sc = new Scanner(System.in);
int i=0,j=0,size=0,k=0,len,l=0;
char[]bufff = new char[20];
String buff=new String();
String buff1=new String();
buff1="";
int buf;
ArrayList<String>forms = new ArrayList<String>();
forms.add(i, sc.nextLine());
while(forms.get(i).charAt(forms.get(i).length() - 1) == ';' || forms.get(i).charAt(forms.get(i).length() - 1) == '<') {
while (forms.get(i).charAt(forms.get(i).length() - 1) == '<'){
forms.set(i,forms.get(i)+sc.nextLine());
}
if (forms.get(i).charAt(forms.get(i).length() - 1) == ';'){
i++;
forms.add(i, sc.nextLine());
}
}
len=forms.size();
ArrayList<String>names=new ArrayList<String>();
ArrayList<Integer>times=new ArrayList<Integer>();
OUTERMOST: for(i=0;i<len;i++){ //проходим по всем формулам
for(j=0;j<forms.get(i).length();j++) {
bufff[k]=forms.get(i).charAt(j);
while(forms.get(i).charAt(j)!=' ' && forms.get(i).charAt(j)!='(' && forms.get(i).charAt(j)!='<' && forms.get(i).charAt(j)!=';'){ //проходим по названию работы
try{
bufff[++k]=forms.get(i).charAt(++j);
}
catch(Exception e){
break OUTERMOST;
}
}
bufff[k]='\0';
if(forms.get(i).charAt(j) == '('){ //если упоминалось впервые-сохраняем работу и считываем время.
size++;
for(l=0;l<k;l++)
buff+=bufff[l];
names.add(buff);
k=0;
j++;
buff="";
bufff[k]=forms.get(i).charAt(j);
while(forms.get(i).charAt(j+1)!=')')
bufff[++k]=forms.get(i).charAt(++j);
for(l=0;l<=k;l++)
buff+=bufff[l];
buf=Integer.valueOf(buff);
times.add(buf);
k=0;
buff="";
j++;
}
else{
k=0;
}
}
}
//for(i=0;i<names.size();i++){
// System.out.println(names.get(i) +" "+times.get(i));
//}
point [] graph=new point[size];
for (i=0;i<size;i++) { //создали граф с именами и временем
graph[i]=new point();
graph[i].name=new String();
graph[i].name=names.get(i);
graph[i].time=times.get(i);
}
OUTERMOST:for(i=0;i<len;i++){//снова проходим по формулам,чтобы выявить все дуги графа.
buff1="";
buff="";
for(j=0,k=0;j<forms.get(i).length();j++,k=0) {
bufff[k]=forms.get(i).charAt(j);
while(forms.get(i).charAt(j)!=' ' && forms.get(i).charAt(j)!='(' && forms.get(i).charAt(j)!=')' && forms.get(i).charAt(j)!='<' && forms.get(i).charAt(j)!=';' && !Character.isDigit(forms.get(i).charAt(j))){ //проходим по названию работы
try{
while(forms.get(i).charAt(j)!=' ' && forms.get(i).charAt(j)!='(' && forms.get(i).charAt(j)!=')' && forms.get(i).charAt(j)!='<' && forms.get(i).charAt(j)!=';')
bufff[++k]=forms.get(i).charAt(++j);
}
catch(Exception e){//повтор кода при вылете!!!!!
if(k!=0){
buff="";
for(l=0;l<k;l++)
buff+=bufff[l];
if(buff1==""){
buff1=buff;
continue;
}
else{
graph[names.indexOf(buff1)].list.add(graph[names.indexOf(buff)]);//заполняем наш граф дугами.
graph[names.indexOf(buff1)].cap++;
buff1=buff;
}
}
break OUTERMOST;
}
}
if(k!=0){
buff="";
for(l=0;l<k;l++)
buff+=bufff[l];
if(buff1==""){
buff1=buff;
continue;
}
else{
graph[names.indexOf(buff1)].list.add(graph[names.indexOf(buff)]);//заполняем наш граф дугами.
graph[names.indexOf(buff1)].cap++;
buff1=buff;
}
}
}
}
//for (i=0;i<size;i++) {
// System.out.println(names.get(i) + " " + times.get(i));
// for (j = 0; j < graph[i].list.size(); j++) {
// System.out.println(" "+graph[i].list.get(j).name);
// }
//}
ArrayList<point>Parents=new ArrayList<point>();
for(i=0;i<size;i++) {
dfs1(graph, graph[i]);
for (j = 0; j < size; j++)
graph[j].mark = 0;
}
for(i=0;i<size;i++)
{
graph[i].mark=0;
if(graph[i].IsParent==1)
Parents.add(graph[i]);
}
/*for(i=0;i<size;i++){
if(graph[i].IsBlue==1)
{
System.out.println(names.get(i) + " " + names.indexOf(names.get(i)));
}
}*/
for(i=0;i<size;i++){
if(graph[i].IsBlue==1){
dfs2(graph,graph[i]);
}
}
/*
for(i=0;i<size;i++){
System.out.println(names.get(i)+" "+graph[i].IsBlue);
}*/
PriorityQueue q = new PriorityQueue(size*size);
point v=new point();
point u=new point();
for(i=0;i<Parents.size();i++){
Parents.get(i).distance=Parents.get(i).time;
if(Parents.get(i).IsBlue==0)
q.insert(Parents.get(i));
}
while(q.count>0) {
v = q.ExtractMax();
v.way.add(v);
if(v.IsBlue==0)
for(i=0;i<v.cap;i++)
{
u=v.list.get(i);
if(u.IsBlue==0)
if(v.distance + u.time == u.distance && !v.equals(u)){
for(j = 0;j < v.way.size();j++)
u.way.add(v.way.get(j));
}
if (v.distance + u.time > u.distance){
u.distance = v.distance + u.time;
u.way.clear();
for(j = 0;j < v.way.size();j++)
u.way.add(v.way.get(j));
q.insert(u);
}
}
}
point answer=graph[0];
for(i=0;i<size;i++){
if(graph[i].distance>answer.distance && graph[i].IsBlue==0){
answer=graph[i];
}
if (graph[i].distance == answer.distance && graph[i]!=answer && graph[i].IsBlue==0) {
for(j=0;j<graph[i].way.size();j++){
answer.way.add(graph[i].way.get(j));
}
}
}
//System.out.println("answer:"+answer.name+" Critical distance:"+answer.distance);
for(i=0;i<answer.way.size();i++){
answer.way.get(i).color=2;
}
System.out.println("digraph {");
for(i=0;i<size;i++){
if(graph[i].color==0 && graph[i].IsBlue==0)//если черная
System.out.println("\t"+graph[i].name + " [label = \"" + graph[i].name + "(" + graph[i].time + ")\"]");
if(graph[i].IsBlue==1){
System.out.println("\t"+graph[i].name + " [label = \"" + graph[i].name + "(" + graph[i].time + ")\", color = blue]");
}
if(graph[i].color==2)
{
System.out.println("\t"+graph[i].name + " [label = \"" + graph[i].name + "(" + graph[i].time + ")\", color = red]");
}
}
for(i=0;i<size;i++){
for(j=0;j<graph[i].list.size();j++){
answer=graph[i].list.get(j);
if(graph[i].IsBlue==1 && answer.IsBlue==1){
System.out.println("\t"+graph[i].name+" -> "+answer.name+" [color = blue]");
}
else if(graph[i].color==2 && answer.color==2){
System.out.println("\t"+graph[i].name+" -> "+answer.name+" [color = red]");
}
else
System.out.println("\t"+graph[i].name+" -> "+answer.name);
}
}
System.out.println("digraph }");
}
public static void dfs1(point [] graph,point Vertex){
int i, size;
point v=Vertex;
point u;
v.dfs1=1;
v.mark=1;
for (i = 0; i < Vertex.cap; i++) {
u = Vertex.list.get(i);
if(u.name==v.name){
v.IsBlue=1;
}
if(u.IsParent==1)
u.IsParent=0;
if(u.mark==0) {
dfs1(graph,u);
}
if(u.mark==1){
u.IsBlue=1;
}
//действия при проходе по ребру
}
v.mark=2;
}
public static void dfs2(point [] graph,point Vertex){
int i, size;
point v=Vertex;
point u;
v.IsBlue=1;
v.mark=1;
for (i = 0; i < Vertex.cap; i++) {
u = Vertex.list.get(i);
if(u.mark==0) {
dfs2(graph,u);
}
//действия при проходе по ребру
}
v.mark=2;
}
}