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 command can be in one of the following two forms:
- p a b -- A portal joining a and b is added to the system. a and b are single words, no more than 255 characters each.
- q a b -- A query asking if a and b are connected by any series of portals built so far. There will be at least one such query in each input set.
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 built.
7 p Waterloo Toronto q Waterloo Toronto p Dubai Toronto p Montreal Vancouver q Montreal Waterloo p Dubai Vancouver q Montreal Waterloo 1 q Waterloo Waterloo
connected not connected connected not connected