Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem I. 379. (September 2015)

I. 379. Many settlers in the West knew each other, but they often had no idea about the whereabouts of some other families. A postal service did not yet exist, and only the neighbors met each other. Having no other alternative, they wanted to map their region as follows.

When two neighbors meet, they exchange information. That is, they both let the other know about the people he or she knows about. If this neighbor did not know about someone earlier, then he or she records the new name together with the name of the person sharing this piece of information. Then, if a settler wants to pass on any information to another settler, the sender asks the person to transmit the message who first informed the sender about the recipient's whereabouts.

After sufficiently many encounters, everybody will know about every other settler in the region.

We assume that initially everybody knows their neighbors, but no other families. The file szomszed.txt describes the neighborhood relations, while the file talalkozas.txt contains the encounters in chronological order (who met whom).

Your program should use the standard input to read who wants to send information to whom. Then the program should determine the number of encounters after which the message can be sent, and the route the message travels from the sender to the recipient.

In the example, line breaks in multiple-line inputs have been replaced by the slash character (/); ``Bemenet'' means input, while ``Kimenet'' is the corresponding output.

The source code of your program, together with a short documentation describing your solution and specifying the developer environment to use for compiling the source, should be submitted in a compressed file

(10 pont)

Deadline expired on October 12, 2015.


12 students sent a solution.
10 points:Németh 729 Gábor, Tersztenyák Balázs.
9 points:Jakab 042 Richárd, Noszály Áron, Rittgasszer Ákos.
8 points:1 student.
6 points:1 student.
4 points:1 student.
2 points:2 students.
1 point:1 student.
0 point:1 student.

Problems in Information Technology of KöMaL, September 2015