Background

A few years ago, because Nanjing was building the subway, many bus routes had to be changed.

JYY was very troubled by this. Imagine getting on a bus, only to find that it is heading in a completely different direction from what you remember.

So JYY plans to develop a bus information app that can be updated in real time using mobile phones. All phones with this app installed can send the latest bus route changes to the database, and can also query the database through the app for the information they need.

Problem Description

There are $n$ bus stops in Nanjing, numbered from $1$ to $n$. Between two different stops $x$ and $y$, there may be a bus that operates directly (going from $x$ to $y$ without passing any other stops). We treat this relationship as an undirected edge (bus routes are obviously bidirectional: we can go from $x$ to $y$, and also from $y$ to $x$).

At any time, each bus stop is connected to at most $2$ edges, and all these edges will not form cycles (bus circular lines are rare, so these bus routes should form several disjoint chains, and the two ends of each chain correspond to two terminal stops).

JYY's iOS app receives a total of $q$ interaction messages in time order. Each message is one of the following five types:

• add x y z: At the current time, a new bus starts operating directly between stop $x$ and stop $y$, and under current traffic conditions, the travel time is $z$.
• del x y: For some reason, the bus that originally operated directly between stop $x$ and stop $y$ has stopped service.
• change x y z: Due to changes in traffic conditions, the current travel time of the bus operating directly between stop $x$ and stop $y$ is $z$.
• reach x y: A user asks whether they can travel from stop $x$ to stop $y$ by bus.
• dest x y: A user gets on at stop $x$ and takes the bus that is currently heading to stop $y$. The user wants to know: after arriving at $y$, if they continue to take available routes (a route that has been taken cannot be taken again), which terminal stop can they finally reach? How long does it take from stop $x$ to reach that terminal stop?

Before the first message is received, there are no buses in service.

Since users may submit incorrect information, JYY wants his software to respond reasonably to incorrect messages as well:

• For an add message, if after adding edge $(x, y)$, the degree of every stop is at most $2$ and there is no cycle in the graph, then JYY considers this message correct and updates the bus route data in the database according to it. Otherwise, JYY will ignore this incorrect message.
• For del and change messages, if there is a bus operating directly between stop $x$ and stop $y$, then JYY considers the message correct and updates the database. Otherwise, JYY will ignore this incorrect message.
• For a dest message, if stop $x$ cannot reach stop $y$, then JYY also considers this query message incorrect.

JYY hopes you can help him complete this bus information app.

Input Format

The first line of the input contains two integers, representing the number of stops $n$ and the number of interaction messages $q$.

The next $q$ lines each contain one message that JYY needs to process. The format is described in the Description section.

Output Format

Output $q$ lines. Each line corresponds to one message in the input file. The required output is as follows:

• If the input message is incorrect, output ERROR.
• For a correct add, del, or change message, output OK.
• For a correct dest message, output one line with two integers: the terminal stop number and the time needed to reach the terminal stop.
• For a reach message, if the two queried bus stops are mutually reachable, output YES, otherwise output NO.

6 10
add 1 2 1
add 2 1 1
add 3 2 1
add 4 5 2
reach 4 6
dest 1 5
del 5 6
add 1 4 2
dest 2 3
dest 3 2

OK
ERROR
OK
OK
NO
ERROR
ERROR
OK
3 1
5 6

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that:

• $2 \leq n \leq 10^5$, $2 \leq q \leq 2 \times 10^5$.
• $1 \leq x, y \leq n$, $x \neq y$, $1 \leq z \leq 10^4$.

Hint

Please pay attention to the impact of input reading on program efficiency.

Translated by ChatGPT 5