using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;

public class CoalescentTreeNode
{
   public string Name { get; set; }

   private CoalescentTree tree;
   public CoalescentTree Tree
   {
      get { return this.tree; }
      internal set { this.tree = value; }
   }

   private CoalescentTreeNode left;
   public CoalescentTreeNode DescendantLeft
   {
      get { return this.left; }
      internal set { this.left = value; }
   }

   private CoalescentTreeNode right;
   public CoalescentTreeNode DescendantRight
   {
      get { return this.right; }
      internal set { this.right = value; }
   }

   private CoalescentTreeNode ancestor;
   public CoalescentTreeNode Ancestor
   {
      get { return this.ancestor; }
      internal set { this.ancestor = value; }
   }

   private double time;
   public double WaitingTime
   {
      get { return this.time; }
      internal set { this.time = value; }
   }

   public bool IsLeaf
   {
      get
      {
         return DescendantLeft == null && DescendantRight == null;
      }
   }

   internal bool HasDescendant
   {
      get
      {
         return DescendantLeft != null && DescendantRight != null;
      }
   }

   public CoalescentTreeNode()
   {
   }

   internal double GetTotalTime()
   {
      double sum = 0.0;
      CoalescentTreeNode current = DescendantLeft;
      while (current != null)
      {
         sum += current.WaitingTime;
         current = current.DescendantLeft;
      }
      return sum;
   }
}

public class CoalescentTree : IFormattable
{
   private readonly List<CoalescentTreeNode> nodes;

   public CoalescentTreeNode Root
   {
      get { return IsIncomplete ? null : this.nodes[0]; }
   }

   public bool IsIncomplete
   {
      get { return this.nodes.Count != 1; }
   }

   public CoalescentTree()
   {
      this.nodes = new List<CoalescentTreeNode>();
   }

   internal CoalescentTree(IEnumerable<CoalescentTreeNode> nodes)
   {
      this.nodes = new List<CoalescentTreeNode>(nodes);
   }

   public CoalescentTreeNode Coalesce(CoalescentTreeNode left, CoalescentTreeNode right, double time)
   {
      if (!Contains(left) || left.Ancestor != null)
      {
         throw new ArgumentException("left");
      }
      if (!Contains(right) || right.Ancestor != null)
      {
         throw new ArgumentException("right");
      }
      double leftTime = left.GetTotalTime();
      if (leftTime > time)
      {
         throw new ArgumentException("left");
      }
      double rightTime = right.GetTotalTime();
      if (rightTime > time)
      {
         throw new ArgumentException("right");
      }
      
      left.WaitingTime = time - leftTime;
      right.WaitingTime = time - rightTime;

      CoalescentTreeNode ancestor = new CoalescentTreeNode()
      {
         DescendantLeft = left,
         DescendantRight = right,
      };
      left.Ancestor = ancestor;
      right.Ancestor = ancestor;

      Remove(left);
      Remove(right);
      Add(ancestor);
      return ancestor;
   }

   public void Add(CoalescentTreeNode node)
   {
      if (node == null)
      {
         throw new ArgumentNullException("node");
      }
      if (node.Tree != null)
      {
         throw new InvalidOperationException();
      }
      this.nodes.Add(node);
      node.Tree = this;
   }

   private bool Remove(CoalescentTreeNode node)
   {
      return this.nodes.Remove(node);
   }

   private bool Contains(CoalescentTreeNode node)
   {
      return this.nodes.Contains(node);
   }

   internal IList<CoalescentTreeNode> GetNodes()
   {
      return new ReadOnlyCollection<CoalescentTreeNode>(nodes);
   }

   public override string ToString()
   {
      return ToString(null, null);
   }

   public string ToString(string format, IFormatProvider formatProvider)
   {
      if (Root.HasDescendant)
      {
         return string.Format("({0},{1});", ToString(Root.DescendantLeft, format, formatProvider), ToString(Root.DescendantRight, format, formatProvider));
      }
      return string.Format("{0}:{1};", Root.Name, Root.WaitingTime);
   }

   private string ToString(CoalescentTreeNode node, string format, IFormatProvider formatProvider)
   {
      if (node == null)
      {
         return string.Empty;
      }
      if (node.HasDescendant)
      {
         return string.Format("({0},{1}):{2}", ToString(node.DescendantLeft, format, formatProvider), ToString(node.DescendantRight, format, formatProvider), node.WaitingTime.ToString(format, formatProvider));
      
      }
      return string.Format("{0}:{1}", node.Name, node.WaitingTime.ToString(format, formatProvider));
   }
}

public class CoalescentSimulator
{
   private readonly Random random;

   public CoalescentSimulator()
   {
      this.random = new Random();
   }

   public CoalescentTree PerformSimulation(IEnumerable<CoalescentTreeNode> samples)
   {
      CoalescentTree tree = new CoalescentTree(samples);

      double time = 0.0;
      while (tree.IsIncomplete)
      {
         IList<CoalescentTreeNode> nodes = tree.GetNodes();
         int count = nodes.Count;
         time = GenerateNextCoalescentEventTime(time, count);
         int leftIndex;
         int rightIndex;
         GetRandomTwoIndexes(count, out leftIndex, out rightIndex);
         tree.Coalesce(nodes[leftIndex], nodes[rightIndex], time);
      }

      return tree;
   }

   private void GetRandomTwoIndexes(int count, out int index1, out int index2)
   {
      index1 = random.Next(count);
      index2 = random.Next(count - 1);
      if (index2 >= index1)
      {
         ++index2;
      }
   }

   private double GenerateNextCoalescentEventTime(double currentTime, int sampleCount)
   {
      double rate = (double)sampleCount * (sampleCount - 1);
      double waitingTime = random.NextExponential(rate);
      return currentTime + waitingTime;
   }
}

public static class RandomExtension
{
   public static double NextExponential(this Random random, double rate)
   {
      double r;
      do
      {
         r = random.NextDouble();
      } while (r == 0.0);
      return -Math.Log(r) / rate;
   }
}

class Program
{
   static void Main()
   {
      CoalescentSimulator simulator = new CoalescentSimulator();
      for (int loop = 0; loop < 10; loop++)
      {
         var nodes = Enumerable.Range(0, 6).Select(i => new CoalescentTreeNode() { Name = (i + 1).ToString() }).ToArray();
         CoalescentTree tree = simulator.PerformSimulation(nodes);
         Console.WriteLine(tree.ToString("0.0000", null));
      }
   }
}