using System;
using System.IO;
using System.Collections.Generic;
using System.Text;

namespace Test_30_1_2008
{
	class Node
	{
		public Dictionary<string, int> Edge = new Dictionary<string, int>();

		public int Component = -1;
		public int ComponentSize;
		public int InDegree = 0;
	}

	class Graph : IComparer<string>
	{
		Dictionary<string, Node> Node = new Dictionary<string, Node>();
		
		public Graph(StreamReader sin)
		{
			Console.Error.WriteLine("Reading from stream...");
		
			string line = sin.ReadLine();
			while (line != null)
			{
				line = line.Trim();
				if (line != "" && !line.StartsWith("#"))
				{
					int sep = line.IndexOf(':');
		
					if (sep == -1)
						AddNode(line);
					else
					{
						string from = line.Substring(0, sep);
		
						foreach (string untrimmedto in line.Substring(sep + 1).Split(';'))
						{
							string to = untrimmedto.Trim();
							if (to != "")
							{
								sep = to.IndexOf(',');
								AddEdge(from, to.Substring(0, sep), int.Parse(to.Substring(sep + 1)));
							}
						}
					}
				}
				
				line = sin.ReadLine();
			}
		}

		void AddNode(string node)
		{
			if (!Node.ContainsKey(node))
				Node[node] = new Node();
		}

		void AddEdge(string from, string to, int weight)
		{
			if (!Node.ContainsKey(from))
				Node[from] = new Node();

			if (!Node.ContainsKey(to))
				Node[to] = new Node();

			Node[from].Edge[to] = weight;
			Node[to].InDegree += weight;

			if (!Node[to].Edge.ContainsKey(from))
				Node[to].Edge[from] = -1;
		}

		static void Center(StreamWriter sout, string str, int width)
		{
			width = width - str.Length;
			sout.Write("".PadLeft(width / 2));
			sout.Write(str);
			sout.Write("".PadLeft((width + 1) / 2));
		}

		public int Compare(string name1, string name2)
		{
			Node node1 = Node[name1];
			Node node2 = Node[name2];

			int ret;

			ret = node1.ComponentSize - node2.ComponentSize;
			if (ret == 0)
			{
				ret = node1.Component - node2.Component;
				if (ret == 0)
				{
					ret = node1.InDegree - node2.InDegree;
					if (ret == 0)
					{
						return string.Compare(name1, name2);
					}
				}
			}

			return ret;
		}

		public void Write(StreamWriter sout)
		{
			List<string> nodes = new List<string>(Node.Keys);

			Console.Error.WriteLine("Sorting...");
			
			nodes.Sort(this);
			
			Console.Error.WriteLine("Determining column widths...");
			
			Dictionary<string, int> widths = new Dictionary<string,int>();

			foreach (string node in Node.Keys)
				widths[node] = node.Length;

			foreach(Node node in Node.Values)
			{
				foreach(KeyValuePair<string, int> to in node.Edge)
				{
					if(to.Value != -1)
					{
						int width = to.Value.ToString().Length;

						if(widths[to.Key] < width)
							widths[to.Key] = width;
					}
				}
			}

			int max = 0;
			foreach (string node in nodes)
				if (node.Length > max)
					max = node.Length;

			Console.Error.WriteLine("Writing to stream...");

			sout.Write("".PadLeft(max));
			foreach (string node in nodes)
			{
				sout.Write(' ');
				Center(sout, node, widths[node]);
			}
			sout.Write(Environment.NewLine);

			foreach (string row in nodes)
			{
				sout.Write(row.PadRight(max));

				foreach (string col in nodes)
				{
					sout.Write(' ');

					if (Node[row].Edge.ContainsKey(col) && Node[row].Edge[col] != -1)
						Center(sout, Node[row].Edge[col].ToString(), widths[col]);
					else
						Center(sout, "-", widths[col]);
				}

				sout.Write(Environment.NewLine);
			}

			sout.Flush();
		}

		int FindComponent(Node node, int id)
		{
			Queue<Node> queue = new Queue<Node>();
			int size = 0;

			queue.Enqueue(node);

			while (queue.Count > 0)
			{
				node = queue.Dequeue();
				size++;

				foreach (string toname in node.Edge.Keys)
				{
					Node tonode = Node[toname];

					if (tonode.Component == -1)
					{
						tonode.Component = id;
						queue.Enqueue(tonode);
					}
				}
			}

			return size;
		}

		public void FindComponents()
		{
			Console.Error.WriteLine("Detecting components...");

			int id = 0;
			List<int> sizes = new List<int>();

			foreach (Node node in Node.Values)
			{
				if (node.Component == -1)
					sizes.Add(FindComponent(node, id++));

				node.ComponentSize = sizes[node.Component];
			}
		}
	}

	class Program
	{
		static void Main(string[] args)
		{
			if (args.Length != 2)
			{
				Console.Error.WriteLine("Syntax: <infile> <outfile>");
				return;
			}

			Graph g = null;

			try
			{
				using (FileStream fin = new FileStream(args[0], FileMode.Open))
				{
					g = new Graph(new StreamReader(fin));
				}
			}
			catch (Exception e)
			{
				Console.Error.WriteLine(e.Message);
				return;
			}

			g.FindComponents();

			try
			{
				using (FileStream fout = new FileStream(args[1], FileMode.Create))
				{
					g.Write(new StreamWriter(fout));
				}
			}
			catch (Exception e)
			{
				Console.Error.WriteLine(e.Message);
			}
		}
	}
}