推荐题目：洛谷 P6231 [JSOI2013] 公交系统
题目背景
几年前南京因为修地铁的缘故，很多公交车线路都被迫改变了。
JYY 为此很苦恼：试想一下，当你坐上一辆公交车，却发现这辆公交车驶向了与你记忆完全不同的方向。
于是 JYY 打算开发一套可以利用手机进行实时更新的公交信息应用， 所有安装了这款应用的手机都可以向数据库发送最新的公交线路更改情况，同时也可以通过应用向数据库查询自己所需要的信息。
题目描述
南京一共有
n
n
n 个公交站点，分别从
1
1
1 到
n
n
n 编号。两个不同的站点
x
x
x 和
y
y
y 之间可能会有公交车直接运营（不经过别的站点直接从
x
x
x 开到
y
y
y） ，我们将这种关系看作一条无向边（公交线路显然是双向的，我们既可以从
x
x
x 坐公交车到
y
y
y，也可以从
y
y
y 坐车到
x
x
x）。
任意时刻任何公交站点都至多只会连有
2
2
2 条边，并且所有这些边是不会形成 环的（公交车很少会出现环线，所以这些公交线路应该形成一些不相交的链，链 的两端分别对应两个终点站）。
JYY 的 IOS 应用按照时间顺序一共收到了
q
q
q 条交互信息，每一条交互信息 都是下列五种信息之一：
- add x y z，表示当前时刻，站点
x
x
x 到站点y
y
y 之间有新增了一班公交车直接运营，并且在当前路况下，公交车所需要的运营时间为z
z
z。 - del x y，表示由于某种原因，原本在站点
x
x
x 和站点y
y
y 之间直接运营的公交车停运了。 - change x y z，表示由于路况情况改变，站点
x
x
x 到站点y
y
y 之间直接运营的公交车当前的运营时间为z
z
z。 - reach x y，表示某个用户询问从站点
x
x
x 坐车能不能坐到站点y
y
y。 - dest x y，表示某个用户从站点
x
x
x 上车，坐上了当前正开往站点y
y
y 的公交车。该用户想知道，他到达y
y
y 后继续乘坐可乘坐的线路(已经乘坐过的线路不能重复乘坐)，最终能够到达的终点站是哪一站？从站点x
x
x 开始需要多久才能 开到终点站？
在收到第一条信息之前，没有任何公交车在运营。
由于用户难免会提交错误的信息，所以 JYY 希望他的软件对于错误的信息也 要能够做出合理的反应：
- 对于 add 信息，如果加入边
(
x
,
y
)
(x,y)
(x,y) 之后，任何站点连接的边数均不超过2
2
2 并且图中没有环，JYY 则认为这个信息是正确的，并根据这个信息更新 数据库中的公交线路数据，否则JYY会无视这个错误信息。 - 对于 del 和 change 信息，如果站点
x
x
x 和站点y
y
y 之间有公交车直接运营， JYY 则认为这条信息是正确的，并更新数据库，否则 JYY 则会无视这个错误 信息。 - 对于 dest 信息，如果站点
x
x
x 不能到达站点y
y
y，JYY 也会认为这一条询问信 息是错误的。
JYY 希望你能够帮助他完成这一个公交信息应用。
输入格式
输入数据的第一行包含两个整数，分别代表站点数
n
n
n 和交互信息条数
q
q
q。
接下来
q
q
q 行，每行对应一个 JYY 需要处理的信息，其格式见【题目描述】。
输出格式
输出
q
q
q 行，每行都对应一个输入文件中的信息，具体内容如下：
- 如果输入的信息是错误的，输出 ERROR。
- 对于一个正确的 add，del，change 信息，输出 OK。
- 对于一个正确的 dest 信息，输出一行两个整数，分别为终点站的编号和开到终点站所需要的时间.
- 对于 reach 信息，如果用户询问的两个公交站点相互可达，输出 YES，否则输出 NO。
输入输出样例 #1
输入 #1
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
输出 #1
OK
ERROR
OK
OK
NO
ERROR
ERROR
OK
3 1
5 6
说明/提示
数据规模与约定
对于
100
%
100\\%
100% 的数据，保证：
-
2
≤
n
≤
10
5
2 \\leq n \\leq 10^5
2≤n≤105，2
≤
q
≤
2
×
10
5
2 \\leq q \\leq2×10^5
2≤q≤2×105。 -
1
≤
x
,
y
≤
n
1 \\leq x, y \\leq n
1≤x,y≤n，x
≠
y
x \\neq y
x=y，1
≤
z
≤
10
4
1\\leq z \\leq10^4
1≤z≤104。
提示
请注意数据读入对程序效率造成的影响。
