SECRETPATHS

Problem

In the kingdom of Philip II of Macedon, there are ~N~ cities and ~N - 1~ secret roads, each connecting a pair of cities bidirectionally. From any city, one can travel to any other city using one or more of these secret roads.

As the kingdom faces attack, Philip is forced to destroy some of the secret roads to hinder the enemy's movement between cities. He assigns this task to his trusted advisor Aristides, brother of Pausanias.

Specifically, Philip can ask Aristides to:

• destroy a specific secret road, or
• answer whether it's possible to travel from one city to another using the remaining secret roads that have not been destroyed yet.

Initially, none of the secret roads have been destroyed.

To ensure that communication between Philip and Aristides cannot be easily intercepted by the enemy, the two actions Philip asks of Aristides are encoded. Please carefully read the description of the input and output of the problem.

Input:

The first line of the input contains three integers separated in pairs by a space: ~N~, the number of cities; ~M~, the number of actions requested by Philip; and an encoding constant ~K~, which can take values ~0~ or ~1~.

Following this are ~N-1~ lines, each corresponding to a secret road. Each of these lines contains two integers ~U~ and ~V~, separated by a space, indicating there is initially a secret road directly connecting cities ~U~ and ~V~. Cities are numbered from ~1~ to ~N~.

Next, there are ~M~ lines, each corresponding to an action requested by Philip. Each of these lines contains a character ~T~ and two integers ~U~ and ~V~. The character ~T~ is one of the uppercase Latin letters "~A~" or "~B~", and the integers ~U~ and ~V~ denote two cities.

When communication starts between Philip and Aristides, the character "~A~" means that Philip requests the destruction of the road between cities ~U~ and ~V~. Sometimes, Philip might get confused and request the destruction of a road that never existed or has already been destroyed; in such cases, no action should be taken. The character "~B~" means that Philip asks whether it is currently possible to travel from city ~U~ to city ~V~ using the remaining roads.

If the encoding constant ~K~ has a value of ~0~, then the interpretation of characters "~A~" and "~B~" is always as described above. However, if ~K~ has a value of ~1~, then the interpretation of characters "~A~" and "~B~" switches each time Aristides positively responds to a question from Philip.

Output:

The output should contain one line for each action requested by Philip that corresponds to a question. The line should contain one word, which will be:

• "yes", if it is possible to travel between the two cities, or
• "no", if it is not possible to travel between the two cities.

Constraints

• ~2 \le N \le 100.000~ και ~2 \le M \le 500.000~
• ~1 \le U \le N~ και ~1 \le V \le N~ για κάθε ενέργεια, και επιπλέον ~U \neq V~
• Time Limit: ~1~ sec.

• Memory Limit: ~256~ MB.

• For test cases with a total value of ~15%~, it will be ~K = 0~ and all destruction actions will precede the questions.

• For test cases with a total value of ~50%~, it will be ~K = 0~.
• For test cases with a total value of ~20%~, it will be ~N \le 1000~ and ~M \le 5000~.
• For test cases with a total value of ~50%~, it will be ~N \le 30.000~.
• For test cases with a total value of ~65%~, it will be ~N \le 70.000~.

Examples of Input - Output Files:

1st

STDIN (secretpaths.in)

8 7 0
3 5
8 4
1 6
2 8
1 8
8 3
7 3
B 5 3
A 3 8
B 2 7
B 1 4
A 8 1
B 1 4
B 6 3

STDOUT (secretpaths.out)

yes
no
yes
no
no

Explanation of the first example

In the first example, ~K = 0~, so the meaning of the characters "~A~" and "~B~" does not change - "~A~" always signifies the destruction of a road and "~B~" always signifies a query.

Therefore, the executed actions are in order:

• Query: Is it possible to travel between cities ~5~ and ~3~? The answer is yes.
• Destruction of the road between cities ~3~ and ~8~.
• Query: Is it possible to travel between cities ~2~ and ~7~? The answer is no.
• Query: Is it possible to travel between cities ~1~ and ~4~? The answer is yes.
• Destruction of the road between cities ~8~ and ~1~.
• Query: Is it possible to travel between cities ~1~ and ~4~? The answer is now no.
• Query: Is it possible to travel between cities ~6~ and ~3~? The answer is no.

2nd

STDIN (secretpaths.in)

8 7 1
3 5
8 4
1 6
2 8
1 8
8 3
7 3
B 5 3
A 3 8
A 3 8
A 2 4
B 2 7
B 1 4
A 6 7

STDOUT (secretpaths.out)

yes
yes
no
yes
no

Explanation of the second example

In the second example, ~K = 1~, so the meaning of the characters "~A~" and "~B~" is reversed every time a query receives a positive answer. The actions executed are as follows:

• Query: Is it possible to travel between cities ~5~ and ~3~? The answer is yes. After this answer, the meanings of "~A~" and "~B~" are reversed.
• Query: Is it possible to travel between cities ~3~ and ~8~? The answer is yes. After this answer, the meanings of "~A~" and "~B~" are reversed again.
• Destruction of the road between cities ~3~ and ~8~.
• Destruction of the road between cities ~2~ and ~4~. This road does not exist, so nothing happens.
• Query: Is it possible to travel between cities ~2~ and ~7~? The answer is no. After this answer, the meanings of "~A~" and "~B~" are not reversed.
• Query: Is it possible to travel between cities ~1~ and ~4~? The answer is yes. After this answer, the meanings of "~A~" and "~B~" are reversed.
• Query: Is it possible to travel between cities ~6~ and ~7~? The answer is no.

Note: The network of cities and roads for both examples that follow is depicted in the following diagram. Only the encoding constant ~K~ and the requested actions change.