Train Trauma

The train network in Sydney has been problematic for some time now, so the government is trying a new 'rapid prototyping approach'. Every day, one of the following will happen:

  1. A new station will be added. This station will initially be unconnected to the rest of the network.
  2. A new track will be added between two existing stations, replacing the previous track coming out from the start station if one existed.

Before the start of day 1, there are two stations: one near your house (initially named "home"), and one at UNSW (initially named "unsw"), which are initially connected by a track. At the start of each day, one of the above operations will occur.

Every day, your task is to determine whether it is possible to make it to UNSW by train.

Input Format

The first line of input is an integer NN, the number of days over which the prototyping will occur.

Following this will be NN lines, which may be any of the following ([x] represents a string):

  • 's [name]', representing the construction of a new station called [name]. [name] will not match any existing station.
  • 't [start]\n[end]', representing the construction of a new track from [start] to [end]. [start] and [end] will both match an existing station. '\n' represents a new line.

Constraints

  • Each station has at most one track leading out from it.
  • NN, the number of days satisfies 1≤N≤1,0001 \leq N \leq 1,000.
  • Station names will be up to 100 characters long.

Output Format

Your output should contain N lines.

On the kth line, you should output "YES" if it is possible to travel from the stop at your house to the stop at UNSW after the change on the kth day, and "NO" otherwise.

Sample Input 0

5
s central
s moore_park
t central
moore_park
t home
central
t moore_park
unsw

Sample Output 0

YES
YES
YES
NO
YES

Explanation 0

On each day, the train's path is:

  1. home -> unsw
  2. home -> unsw
  3. home -> unsw
  4. home -> central -> moore_park
  5. home -> central -> moore_park -> unsw

Sample Input 1

6
s central
t home
central
s surry_hills
t central
surry_hills
t surry_hills
home
t surry_hills
unsw

Sample Output 1

YES
NO
NO
NO
NO
YES

Explanation 1

On each day, the train's path is:

  1. home -> unsw
  2. home -> central
  3. home -> central
  4. home -> central -> surry_hills
  5. home -> central -> surry_hills -> home -> (repeats infinitely)
  6. home -> central -> surry_hills -> unsw