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:
- 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 build 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 build.
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