New cults P70868


pdf   zip


It is year 5000 A.D. Against all odds, mankind has survived, multiplied, and spread across the Solar System. New faiths, cults and alike coexist with religions that were considered traditional thousands of years ago. Among them, the cult to Masao, the legendary hero of the 21st century. (For his believers, now it is year 3017 A.M.) The problem is, the cult to Masao has so many factions and subfactions, that it is difficult to keep track of which was originated from which.

Consider the following example, which is just a tiny simplification, with two main trees of the cult to Masao:

[levelsep=40pt,treesep=20pt,arrows=−>]Masaoism Masochism Garrulism        [levelsep=40pt,treesep=20pt,arrows=−>]Longlongism Charism Longism Intism

Among other relations, we can see that Garrulism was directly originated from Masaoism, Intism was originated from Longlongism after two steps, Charism and Longism belong to different branches of the same tree, and Masochism and Intism belong to different trees.

Please write a program that, given the origin of the factions of the cult to Masao, computes the relation among several pairs of factions.


Input consists of several cases. Every case begins with a number m, followed by m pairs of names n1 and n2, which indicate that n2 was directly originated from n1. Next comes the number of queries of the case q, followed by q pairs of names s1 and s2, with s1s2. Assume 0 ≤ m ≤ 105, that q is similar to m for the large private test cases, that the relations correctly define one or more trees, and that no tree has more than 104 levels.


For every query pair, print the relation between s1 and s2. Suppose that a name not present in the description of the factions is an isolated tree by itself. Print a line with 10 dashes after the output for every case.

Public test cases
  • Input

    Longism Intism
    Masaoism Garrulism
    Longlongism Charism
    Masaoism Masochism
    Longlongism Longism
    Masaoism Garrulism
    Intism Longlongism
    Charism Longism
    Masochism Intism
    z y


    Masaoism is 1 level(s) above Garrulism
    Longlongism is 2 level(s) above Intism
    Charism and Longism : same tree, different branches
    Masochism and Intism : different trees
    z and y : different trees
  • Information
    Salvador Roura
    Official solutions
    User solutions
    Vuitè Concurs de Programació de la UPC - Final