DWITE, November 2011, Problem 5

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 will contain 5 test sets. The first line of each set is a number ~1 \le N \le 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 build so far. There will be at least one such query in each input set.

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

Sample Input

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

Sample Output

connected
not connected
connected
connected

Problem Resource: DWITE