// compute the stationary distribution of a given input graph using a
// Monte-Carlo computation.  In practice, we simulate N random walks of
// length L, and compute the proportion of visits P_i over the N random
// walks for every node i.
//
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <sstream>
#include <random>

using namespace std;

vector<string> V;		  // vertex names
map<string, unsigned int> V_idx;  // vertex index: name -> position in V
vector<vector<unsigned int>> Adj; // adjacency list

unsigned int get_vertex(const string & name) {
    unsigned int v;
    auto pib = V_idx.insert(make_pair(name, Adj.size()));
    if (pib.second) {
	v = V.size();
	V.push_back(name);
	Adj.resize(v+1);
    } else {
	v = pib.first->second;
    }
    return v;
}

void add_arc(unsigned int v, unsigned int w) {
    Adj[v].push_back(w);
}

// read the graph from standard input.  Each line represents the
// adjacency list of a vertex in the graph.  For example,
// 
// A B C
// 
// means that there are two arcs departing vertex A and going to
// vertexes B and C, respectively.
//
istream & read_graph(istream & input) {
    string v_name, w_name;
    unsigned int v, w;
    string line;
    while (getline(input, line)) {
	istringstream l_input(line);
	if (! (l_input >> v_name)) 
	    continue;
	v = get_vertex(v_name);
	while (l_input >> w_name) {
	    w = get_vertex(w_name);
	    add_arc(v, w);
	}
    }
    return input;
}

int main (int argc, const char * argv[]) {
    int N = 10000;
    int L = 1000;

    if (argc > 1) {
	const string a1(argv[1]);
	N = stoi(a1);
	if (argc > 2) {
	    const string a2(argv[2]);
	    L = stoi(a2);
	}
    }

    read_graph(cin);

    vector<unsigned int> C(V.size());

    std::random_device rd;
    std::mt19937 gen(rd());

    for (int i = 0; i < N; ++i) {
	unsigned int v = 0;
	for (int len = 0; len < L; ++len) {
	    std::uniform_int_distribution<> dis(0, Adj[v].size() - 1);
	    v = Adj[v][dis(gen)];
	}
	C[v] += 1;
    }
    for (unsigned int v = 0; v < V.size(); ++v)
	cout << V[v] << " " << 1.0*C[v]/N << endl;
}