Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
106 - ZOJ Monthly, May 2011 - J
Island Communication

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Once upon a time, human have not invented boats and planes, bridges were the most important things in communication among islands. There is a large kingdom consists of N islands. One day, a terrible war broken out in this country. Due to the war, there might be several bridges being built or destroyed in each day. Tom, one of your best friends, is a business man. People always earn lots of money during the war, and certainly Tom doesn't want to lose this chance. But he doesn't know whether he can get to one island from another island, so he comes to you for help.

Input

There are multiple cases. The first line of each case consists of two integers N and M (1≤N≤500, 1≤M≤50000), indicates the number of islands and the number of operations. The indies of the island are from 1 to N. Then comes M lines of operations. There are three kinds of operations:

  1. I x y: means they build a bridge connects island x and island y
  2. D x y: means they destroy the bridge which connects island x and island y
  3. Q x y: Tom want to know whether he can get to island y from island x

Assume there are no bridges at the beginning, and each bridge will be built at most once(means when one bridge is destroyed, you can never build it any more)

Output

In the first line, you must output the case number. And for each query, you must output "YES" if you can get to island y from island x. otherwise output "NO".

Print a blank line between cases.

Sample Input

5 9
I 1 2
I 2 3
Q 1 3
I 1 3
I 2 4
I 4 5
D 1 2
D 2 3
Q 1 5

Sample Output

Case 1:
YES
NO

Author: YANG, Kete
Submit    Status