// Arup Guha
// 8/1/2026
// Solution to 1989 UCF HS Programming Contest Problem: Say What???

import java.util.*;

public class saywhat {

	public static ArrayList<edge>[] g; 
	
	public static void main(String[] args) {
	
		// Get size.
		Scanner stdin = new Scanner(System.in);
		
		// Annoying.
		while (stdin.hasNext()) {
		
			// Initialize our graph.
			g = new ArrayList[26];
			for (int i=0; i<26; i++)
				g[i] = new ArrayList<edge>();
			
			// Get line and set up tokenizer.
			String line = stdin.nextLine();
			StringTokenizer tok = new StringTokenizer(line);
			
			// Annoying.
			while (tok.countTokens() > 0) {
			
				// Get the name.
				String name = tok.nextToken();
				
				// Get languages.
				ArrayList<Integer> langs = new ArrayList<Integer>();
				while (tok.countTokens() > 0) 
					langs.add(tok.nextToken().charAt(0)-'A');
					
				// Add all possible translations this person could do.
				for (int i=0; i<langs.size(); i++) {
					for (int j=0; j<langs.size(); j++) {
						if (i == j) continue;
						int x = langs.get(i), y = langs.get(j);
						g[x].add(new edge(x, y, name));
						g[y].add(new edge(y, x, name));
					}
				}
			
				// Get next line.
				line = stdin.nextLine();
				tok = new StringTokenizer(line);
			}
			
			// Now we are ready to solve the case.
			boolean canDo = solve();
			
			// Specification doesn't state this but the sample indicates a blank line after
			// each case.
			System.out.println();
		}
	}
	
	public static boolean solve() {
		
		// prev[b] is the edge that got me to b.
		edge[] prev = new edge[26];
		Arrays.fill(prev, null);
		prev[0] = new edge(0,0,"Durk");
		ArrayDeque<Integer> q = new ArrayDeque<Integer>();
		q.offer(0);
		
		// Run BFS.
		while (q.size() > 0) {
			
			// Where I got to.
			int cur = q.poll();
			
			// Try each edge.
			for (edge e: g[cur]) {
				
				// We can get somewhere new.
				if (prev[e.to] == null) {
					prev[e.to] = e;
					q.offer(e.to);
				}
			}
		}
		
		// Get this out of the way.
		if (prev[25] == null) {
			System.out.println("Path does not exist.");
			return false;
		}
		
		// Do path reconstruction.
		String last = prev[25].who;
		int idx = 25;
		ArrayList<String> pathBack = new ArrayList<String>();
		pathBack.add(last+" speaks to King");
		
		// Go backwards.
		while (idx != 0) {
			
			// Where I came from.
			idx = prev[idx].from;
			String cur = prev[idx].who;
			
			// Add this speaking edge.
			pathBack.add(cur+" speaks to "+last);
			
			// Reassign for next iteration.
			last = cur;
		}
		
		// Print it.
		System.out.println("Path exists:");
		for (int i=pathBack.size()-1; i>=0; i--)
			System.out.println(pathBack.get(i));
		
		return true;
	}
}

class edge {
	
	public int from;
	public int to;
	public String who;
	
	public edge(int u, int v, String w) {
		from = u;
		to = v;
		who = w;
	}
}