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 ≤ 100,000 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