import java.util.*;
import java.io.*;

import jdsl.core.api.*;
import jdsl.core.ref.*;
import jdsl.graph.algo.*;
import jdsl.graph.api.*;
import jdsl.graph.ref.*;


class Node {
	public static int TRANSIT_NODE = 0, STUB_NODE = 1;
	String name;
	int type;

	 Node(int type, String name) {
		this.type = type;
		this.name = name;
	} public boolean equals(Object o) {
		return this.name.equals("" + o);
	} public String toString() {
		return name;
	}
} 

class Link {
	Node from, to;
	int length;

	Set children, receivers;

	 Link(Node from, Node to, int length) {
		this.from = from;
		this.to = to;
		this.length = length;

		this.children = new HashSet();
		this.receivers = new HashSet();
	} 
	public boolean addChild(Link child) {
		return children.add(child);
	} 
	public boolean addReceiver(Receiver receiver) {
		return receivers.add(receiver);
	} 
	public boolean equals(Object o) {
		Link other = (Link) o;

		 return this.from.equals(other.from)
		&& this.to.equals(other.to)
		|| this.from.equals(other.to)
		    && this.to.equals(other.from);
	} 
	public String toString() {
		return from + "<--->" + to;
	}
} 

class MyPathfinder extends IntegerDijkstraPathfinder {
	protected int weight(Edge e) { return ((Link) e.element()).length; }
} 

class Receiver {
	int startTime;
	Vertex vertex;
	int pathLen = 0;

	Receiver(Vertex vertex, int startTime) {
		this.vertex = vertex;
		this.startTime = startTime;
	} 
	public boolean equals(Object o) {
		Receiver other = (Receiver) o;
		return this.vertex.equals(other.vertex)
		&& this.startTime == other.startTime;
	}
} 

class Filter {
	static final int MAX_WINDOWS = 100;
	int[] window = new int[MAX_WINDOWS];
	int nWindows = 0;

	int[] nLinks = new int[MAX_WINDOWS];

	double totalBandwidth;

	 Filter() {

	} Filter(int[]window, int nWindows) {
		for (int i = 0; i < nWindows; i++) {
			this.window[i] = window[i];
			this.nWindows++;
		}
	}

	int addWindow(int theWindow) {
		if (nWindows == MAX_WINDOWS) {
			return -1;
		}

		window[nWindows++] = theWindow;
		return nWindows;
	}
}

class Mtree {
	Graph graph;
	Vertex sender;
	Set links, receivers;

	Filter filter;
	int nLinks;
	Link rootLink;

	private MyPathfinder finder;

	 Mtree(Graph graph, Vertex sender) {
		this(graph, sender, null);
	} Mtree(Graph graph, Vertex sender, Filter filter) {
		this.graph = graph;
		this.sender = sender;
		this.filter = filter;

		links = new HashSet();
		receivers = new HashSet();

		rootLink =
		    new Link((Node) sender.element(),
			     (Node) sender.element(), 0);
		finder = new MyPathfinder();
	}

	void setFilter(Filter filter) { this.filter = filter; }
	boolean addReceiver(Receiver receiver) { 
		if (receivers.contains(receiver)) 
			return false;

		finder.execute(graph, sender, receiver.vertex);
		receivers.add(receiver);

		Link prev = rootLink;

		for (EdgeIterator e = finder.reportPath(); e.hasNext();) {
			Link current = (Link) e.nextEdge().element();
			 links.add(current);
			 nLinks++;
			 prev.addChild(current);
			 prev = current;
			 receiver.pathLen++;
		} prev.addReceiver(receiver);
		return true;
	}

	Set traverse(int time, Filter filter) {
		Set treeLinks = new HashSet();
		 treeTraverse(time, rootLink, treeLinks, filter);
		 return treeLinks;
	}
	    void treeTraverse(int time, Link root, Set treeLinks,
			      Filter filter) {
		int[] prevLinks = new int[filter.nWindows];

		for (int i = 0; i < filter.nWindows; i++)
			 prevLinks[i] = filter.nLinks[i];

		for (Iterator children = root.children.iterator();
		     children.hasNext();) {
			Link child = (Link) children.next();
			 treeTraverse(time, child, treeLinks, filter);
		} for (int i = 0; i < filter.nWindows; i++) {
			if (filter.nLinks[i] > prevLinks[i]) {
				treeLinks.add(root);
				filter.nLinks[i]++;
			} else {
				for (Iterator receivers = root.receivers.iterator(); receivers.hasNext();) {
					Receiver receiver = (Receiver) receivers.next();
					if (receiver.startTime <= time && receiver.startTime >= time - filter.window[i]) {
						treeLinks.add(root);
						filter.nLinks[i]++;
						break;
					}
				}
			}
		}
	}
}

class GraphInfo {
	Graph graph;
	Map vertex, edge;
	int nVertices, nEdges;

	 Vertex[] indexedVertex;

	 GraphInfo(int maxVertices) {
		vertex = new HashMap();
		edge = new HashMap();
		graph = new IncidenceListGraph();

		this.indexedVertex = new Vertex[maxVertices];
		this.nVertices = 0;
		this.nEdges = 0;
		}
	    int insertVertex(Node node)
	{ if (!vertex.containsKey("" + node)) {
			vertex.put("" + node, indexedVertex[nVertices++] =
				   graph.insertVertex(node));
			//System.err.println("Putting..." + node + " # " + nVertices);
		}
		return nVertices;
	}

		int insertEdge(Link link) { if (!edge.containsKey(link)) {
			Vertex src = (Vertex) vertex.get("" + link.from);
			Vertex dst = (Vertex) vertex.get("" + link.to);
			 edge.put(link, graph.insertEdge(src, dst, link));
			 nEdges++;
		}
		return nEdges;
	}
}

class SimulParams {
	int maxTrials = 100;
	int maxTimes;
	int maxReceivers;
	int delay;

	static final int MAX_FILTERS = 100;
	 Filter[] filter;
	int nFilters;


	 SimulParams(int maxReceivers, int maxTimes, int maxTrials,
		     int delay, Filter[]filter) {
		this.maxReceivers = maxReceivers;
		this.maxTimes = maxTimes;
		this.maxTrials = maxTrials;
		this.delay = delay;
		this.nFilters = filter.length;
		this.filter = filter;
	}
	    SimulParams(int maxReceivers, int maxTimes, int delay,
			Filter[]filter) {
		this(maxReceivers, maxTimes, 100, delay, filter);
	}

	SimulParams(int maxReceivers, int maxTimes, Filter[]filter) {
		this(maxReceivers, maxTimes, 100, 1, filter);
	}
}

public class GraphSim {

	public static void main(String[]args) throws IOException
	{ if (args.length < 3) {
			System.err.println
			    ("Usage: java GraphSim <maxRcv> <maxTimes> <delay> <window>...");
			System.exit(-1);
		}

		BufferedReader reader =
		    new BufferedReader(new InputStreamReader(System.in));
		int maxReceivers = Integer.parseInt(args[0]);
		int maxTimes = Integer.parseInt(args[1]);
		int delay = Integer.parseInt(args[2]);

		int nFilters = 1;
		 Filter[] filter = new Filter[nFilters];
		 filter[0] = new Filter();

		for (int i = 3; i < args.length; i++) {
			int window = Integer.parseInt(args[i]);
			 filter[0].addWindow(window);
		}
		    SimulParams params =
		    new SimulParams(maxReceivers, maxTimes, delay, filter);
		GraphSim sim = new GraphSim(reader, params);

		for (int i = 0; i < filter.length; i++) {
			for (int j = 0; j < filter[i].nWindows; j++) {
				//System.out.println("#" + filter[i].window[j] + " " + filter[i].nLinks[j]);

			}
			System.out.println("#" + filter[i].nWindows + " " +
					   filter[i].totalBandwidth);
		}
	}

	GraphSim(BufferedReader reader,
		 SimulParams params) throws IOException {
		//GraphInfo info = new ITMGraphCreater().createGraphInfoFromSpec(reader);
		GraphInfo info = new MBoneGraphCreater().createGraphInfoFromSpec(reader);
		Mtree tree = constructTree(info, params.maxReceivers,
					   params.maxTimes);
		Set receivers = tree.receivers;

		for (int i = 0; i < params.nFilters; i++) {
		   Filter filter = params.filter[i];
		   for (int trial = 0; trial < params.maxTrials; trial++) {
		   	int time = (int)(((double)params.maxTimes)*Math.random());
			   Set treeLinks = tree.traverse(time, filter);
		   }
		   filter.totalBandwidth = calculateBandwidth(filter, params);
		   filter.totalBandwidth /= params.maxTrials;
		} 
	 }
	double calculateBandwidth(Filter filter, SimulParams params)
	{
		double bandwidth = 1.0 * filter.nLinks[0] * Math.log(1.0 * filter.window[0] / params.delay);
		for (int i = 1; i < filter.nWindows; i++) {
			bandwidth += 1.0 * filter.nLinks[i] * Math.log(1.0 * filter.window[i] / filter.window[i - 1]);
		} 
		return bandwidth;
	}

	Mtree constructTree(GraphInfo info, int maxReceivers, int maxTimes) 
	{
		int index;
		Mtree tree;

		while (true) {
			index =
			    (int) (((double) info.nVertices) *
				   Math.random());
			if (info.indexedVertex[index] == null)
				continue;
			if (((Node) info.indexedVertex[index].element()).
			    type == Node.STUB_NODE) {
				tree =
				    new Mtree(info.graph,
					      info.indexedVertex[index]);
				break;
			}
		} 
		
		for (int i = 0; i < maxReceivers; i++) {
			Vertex rcv;
			index = (int) ( (((double) info.nVertices) * Math.random()));
			if ((rcv = info.indexedVertex[index]) == null)
				continue;

			if (((Node) rcv.element()).type == Node.STUB_NODE) {
				int time = (int) (((double) maxTimes) * Math.random());
				Receiver receiver = new Receiver(rcv, time);
				tree.addReceiver(receiver);
				System.err.println(tree.receivers.size() + " " + tree.links.size() +
									   " " + tree.nLinks);
			}
		}
		return tree;
	}

	void printVertices(Graph graph) { System.out.println("VERTICES");
		for (VertexIterator vi = graph.vertices(); vi.hasNext();) {
			System.out.println(
					   ((Node)
					    ((Vertex) vi.nextVertex()).
					    element()).name);
		}
	}
} 

class ITMGraphCreater 
{
	GraphInfo createGraphInfoFromSpec(BufferedReader reader) throws IOException 
	{
		Node node;
		Link link;

		String str;
		GraphInfo info = null;

		int state = -1;

		while ((str = reader.readLine()) != null) {
			String name;

			if (str.indexOf("GRAPH") >= 0) {
				state++;
				continue;
			}

			if (str.indexOf("VERTICES") >= 0) {
				state++;
				continue;
			}

			if (str.indexOf("EDGES") >= 0) {
				state++;
				continue;
			}

			if (state == 0) {
				GraphInfo junk;
				if ((junk = createGraphInfoFromSpec(str))
				    != null) {
					info = junk;
				}
			} else if (state == 1) {
				if ((node = createNodeFromSpec(info, str))
				    != null && info != null)
					info.insertVertex(node);
			} else if (state == 2) {
				if ((link = createLinkFromSpec(info, str))
				    != null) {
					info.insertEdge(link);
				}
			}
		}
		return info;
	}

	GraphInfo createGraphInfoFromSpec(String str) 
	{
		int nVertices = 0, nEdges = 0;
		StringTokenizer st = new StringTokenizer(str);
		try {
			nVertices = Integer.parseInt(st.nextToken());
			nEdges = Integer.parseInt(st.nextToken());
		} catch(NumberFormatException e) {
			return null;
		} catch(NoSuchElementException e) {
			return null;
		}
		return new GraphInfo(nVertices);
	}

	Node createNodeFromSpec(GraphInfo info, String str) {

		String name, spec;
		int type;

		StringTokenizer st = new StringTokenizer(str);
		 try {
			name = st.nextToken();
			spec = st.nextToken();
			if (spec.indexOf("S:") >= 0) {
				type = Node.STUB_NODE;
			} else {
				type = Node.TRANSIT_NODE;
			}

		} catch(NumberFormatException e) {
			return null;
		} catch(NoSuchElementException e) {
			return null;
		}
		//System.err.println(name);
		return new Node(type, name);
	}

	Link createLinkFromSpec(GraphInfo info, String str) {
		String from, to;
		int length;

		StringTokenizer st = new StringTokenizer(str);
		 try {
			from = st.nextToken();
			to = st.nextToken();
			length = Integer.parseInt(st.nextToken());
		} catch(NumberFormatException e) {
			return null;
		} catch(NoSuchElementException e) {
			return null;
		}

		//System.err.println(from);
		//System.err.println(to);
		//System.err.println((Vertex)info.vertex.get(from));
		//System.err.println((Vertex)info.vertex.get(to));

		return new Link((Node) ((Vertex) info.vertex.get(from)).
				element(),
				(Node) ((Vertex) info.vertex.get(to)).
				element(), length);
	}
}


class MBoneGraphCreater {
	GraphInfo createGraphInfoFromSpec(BufferedReader reader) throws IOException {
		String str;

		int edgeIndex = 0;
		int maxVertices = 50000;
		GraphInfo info = new GraphInfo(maxVertices);

		while ((str = reader.readLine()) != null) {
			StringTokenizer st =
			    new StringTokenizer(str, ": \n\r");
			String srcName = st.nextToken();
			Node src = new Node(Node.STUB_NODE, srcName);

			while (st.hasMoreTokens()) {
				String dstName = st.nextToken();
				Node dst = new Node(Node.STUB_NODE, dstName);
				Link link = new Link(src, dst, 1);
				info.insertVertex(src);
				info.insertVertex(dst);
				info.insertEdge(link);
			}
		} 
		return info;
	}
}