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

Problem S. 67. (December 2011)

S. 67. In the old times when computer networks mainly consisted of chains of computers connected by coaxial cables and BNC connectors, one of the favorite hobbies of the Evil SysAdmin was changing the network topology on the fly, then monitoring user reactions.

Newer and newer network building methods however rendered this amusement less joyful, so the Evil SysAdmin retried the hobby in a virtual environment. Your task is to develop a program component to simulate the state of the network and user reactions.

The simulation begins with an ``empty network'' consisting of N disconnected computers. It prompts for M network building and diagnostic operations. The goal is to determine whether each operation can be realized, and if yes, perform the network building operations.

The network building operations are detailed below:

-- add <A> <B>\ with 1\leA\neB\leN being the number of the two computers, between which a new bidirectional connection should be established. The operation can be realized if at most 1 cable is connected to each of the computers, and the new connection does not result in a cycle.

-- remove <A> <B>\ with 1\leA\neB\leN being the number of the two computers, between which the direct connection should be removed. The operation can be realized if there is a cable between A and B.

The following diagnostic operation determines whether there will be user reactions in the near future:

-- ping <A> <B>\ with 1\leA\neB\leN being the number of the two computers, between which mutual accessibility is tested. The operation can be realized if there is a route between A and B.

You should give a ``yes'' or ``no'' answer depending on their realizability.

The inputs of your program 2\le N\le 1\;000\;000 and 0\le M\le 1\;000\;000 are given through the first line of the standard input, separated by a space. The following M lines then describe an operation (one operation per line) in the above format.

The standard output should contain exactly M lines: each should contain the result of the corresponding operation. In order to obtain the maximal number of points, your program should give the proper answer in a few seconds even for the largest inputs.

In the example, ``Példa bemenet'' is a sample input, while ``Példa kimenet'' is the corresponding output.

In a compressed folder, the source code (s67.pas, s67.cpp, ...) of your solution -- without the .exe or any other auxiliary files generated by the compiler -- should be submitted together with a short documentation (s67.txt, s67.pdf, ...) also describing which developer environment to use for compiling.

(10 pont)

Deadline expired on January 10, 2012.


11 students sent a solution.
10 points:Marussy Kristóf.
9 points:Adrián Patrik.
8 points:1 student.
7 points:5 students.
6 points:3 students.

Problems in Information Technology of KöMaL, December 2011