November 2011
Problem 5
Portals Check

Scientists have finally discovered a method of creating a portal between two places (on Earth, as apparently the physics gets tricky when we get to space). Before mass producing their device the scientists want you to create software that checks whether two places are connected via a series of their portals. Help them with this project (Note: Portals are bidirectional, so they can be travelled through in both directions).

The input file DATA5.txt will contain 5 test sets. The first line of each set is a number 1 <= N <= 100000 representing the number of commands your software has to run, followed by N commands. Each commands can be in one of the following two forms:

The output file OUT5.txt will contain 5 sets of outputs, answering each query command with connected or not connected.

Note: in the second test case, Waterloo is not connected to itself, as no portals have been build.

Sample Input (first 2 shown):
p Waterloo Toronto
q Waterloo Toronto
p Dubai Toronto
p Montreal Vancouver
q Montreal Waterloo
p Dubai Vancouver
q Montreal Waterloo
q Waterloo Waterloo
Sample Output (first 2 shown):
not connected
not connected