This is an interactive problem.

When preparing to New Year Eve, Queen Amidala always checks her electric garland to ensure it works. The garland consist of n lamps which are numbered from 1 to n; there are (n - 1) pairs of them which are allowed to be connected with wires to form a special structure. Each wire in the structure connects exactly two different lamps, and all the lamps are connected together with the wires.

However, the garland is so huge that this year, the Queen decided not to build the whole structure at once. However, she still needs to check each wire. So, she will connect some of the wires, then check if electric current can pass from some lamps to some others, then disconnect some of the connected wires, connect other ones and so on. More formally, the Queen will perform a sequence of operations. Each operation will be one of the following:

• Connect two different lamps with a wire;
• Remove a wire that connects two lamps;
• Test if electric current can pass between two lamps by the wires that are currently connected.

The Queen was almost starting to check the garland, but she realized that not all her tests will be meaningful because some pairs of lamps will be disconnected at the time she checks them, and the current will not pass even if the garland is in fact working. She asked Anakin Skywalker to help in checking her plan of checking the garland. Anakin is sure that it's boring to proceed all the operations manually, so he asked you to write a program which will process all three types of operations described above; for each test operation, the program must answer whether the two lamps are connected by wires of not. Anakin shouldn't disgrace himself in Amidala's eyes, so don't let him down!

At start, your program will be given an integer n (1 ≤ n ≤ 100 000). After that, you have to process queries one by one. Each query will be entered on a separate line in one of the following forms:

• "C a b", where a and b are integers (1 ≤ a, b ≤ n, a ≠ b). This query means that the Queen is connecting lamps a and b with a wire. There will be exactly (n - 1) such queries.
• "D a b", where a and b are integers (1 ≤ a, b ≤ n, a ≠ b). This query means that the Queen is disconnecting lamps a and b. It's guaranteed that at the moment this query is entered, lamps a and b are connected by a wire; note that pairs (a, b) and (b, a) correspond to the same wire. There will be exactly (n - 1) such queries.
• "T a b", where a and b are integers (1 ≤ a, b ≤ n). This query means that the Queen is testing if electric current can pass between lamps a and b. You must print a line containing "YES" (without quotes) if lamps a and b are reachable from each other by wires, and "NO" otherwise. Do not forget to flush your output.
• "E", this means the end of checking, your program must immediately terminate after receiving this query.

There will be no more than 300 000 queries.

It is guaranteed that the queries will always follow the garland's structure, and each possible wire will be connected and disconnected exactly once.

Initially, all possible wires are disconnected.