Greenhound Web Service

Time Limit: 5 Seconds    Memory Limit: 32768 KB

Well, I am sure you all know Greyhound, the largest intercity bus transportation. However, few people know about Greenhound, which is actually Greyhound's mother company. It runs the expressway network. What makes Greenhound so special is that it charges the same price no matter how far you go, as long as you stay on the Greenhound expressways. As Greenhound manages a large network, it is quite convenient and economical for travelers.

In an effort to bring up the business online, a web service system is under architecture. People frequently query whether they could drive from one city to another via Greenhound expressway. Although Greenhound has a large network, it is not willing to invest too much on duplications. People would like to check about such information at the entrance to the expressway. For each query, a request is generated and posted to the Greenhound headquarter in the Silicon Valley, where its application servers reside. You are in charge of the development of the service layer, which is supposed to generate the responses.

You have your group solved the interface to external dependencies so that your focus is on the algorithm part. What you will take extra care is that Greenhound's expressways are up to certain changes. To make it simple enough to handle, all the changes during a month is fed into the system at the beginning of the month. There will not be any synchronization issue since the web service is turned off during the maintenance hours. Then, for the rest of the month, your sole responsibility is responding to the queries.

There are four kinds of change to the Greenhound network:

NEW - A new expressway is put into use. No expressways are connecting the same two cities.
DELETE - An expressway is out-dated and potentially dangerous. It is abandoned.
CLOSE - An expressway is closed for maintenance. Notice that if the expressway from city A to city B is closed, you could still get from city B to city A on the other side. Only half of the road is closed.
OPEN - A closed expressway is back into use.

Input

The first line of the input contains a single integer n (2 <= n <= 100) - the number of cities in the Greenhound network. The rest of the input contains queries or maintenance requests. (0 <= a, b < n)

N a b - A new expressway connecting city a and b is put into use.
D a b - Expressway between city a and b is abandoned.
C a b - Expressway from a to b is closed for maintenance.
O a b - Expressway from a to b is back to use.
Q a b - Query for whether it is possible to drive from city a to city b via Greenhound network.
X indicates the end of input.

Notice the initial road map is inserted at first with a few maintenance requests also.

Output

For each query, print 1 if it is possible, 0 otherwise.

Sample Input

3
N 0 1
N 1 2
Q 2 0
C 1 2
Q 2 0
Q 0 2
X

Sample Output

1
1
0

Submit

Source: ZOJ Monthly, October 2004