题目描述

【故事背景】 几年前南京因为修地铁的缘故，很多公交车线路都被迫改变了。JYY为此很 苦恼：试想一下，当你坐上一辆公交车，却发现这辆公交车驶向了与你记忆完全 不同的方向。于是 JYY 打算开发一套可以利用手机进行实时更新的公交信息 应用， 所有安装了这款应用的手机都可以向数据库发送最新的公交线路更改情况， 同时也可以通过应用向数据库查询自己所需要的信息。 【问题描述】 南京一共有 N 个公交站点，分别从1到 N 编号。两个不同的站点 x和y之间 可能会有公交车直接运营（不经过别的站点直接从 x 开到 y） ，我们将这种关系 看作一条无向边（公交线路显然是双向的，我们既可以从 x坐公交车到 y，也可 以从y坐车到x） 。 任意时刻任何公交站点都至多只会连有 2条边，并且所有这些边是不会形成 环的（公交车很少会出现环线，所以这些公交线路应该形成一些不相交的链，链 的两端分别对应两个终点站）。 JYY 的 IOS 应用按照时间顺序一共收到了 Q 条交互信息，每一条交互信息 都是下列五种信息之一： 1)  add x y z 表示当前时刻，站点 x 到站点 y 之间有新增了一班公交车直接运营，并 且在当前路况下，公交车所需要的运营时间为 z； 2)  del x y 表示由于某种原因，原本在站点 x 和站点 y 之间直接运营的公交车停运 了； 3)  change x y z 表示由于路况情况改变，站点 x 到站点 y 之间直接运营的公交车当前的 运营时间为 z； 4)  reach x y 表示某个用户询问从站点 x坐车能不能坐到站点y； 5)  dest x y 表示某个用户从站点 x 上车，坐上了当前正开往站点 y 的公交车。该用 户想知道，他到达 y 后继续乘坐可乘坐的线路(已经乘坐过的线路不能重 复乘坐)，最终能够到达的终点站是哪一站？从站点 x 开始需要多久才能 开到终点站？ 由于用户难免会提交错误的信息，所以 JYY希望他的软件对于错误的信息也 要能够做出合理的反应： 1)  对于 add 信息，如果加入边(x,y)之后，任何站点连接的边数均不超过 2 并且图中没有环，JYY 则认为这个信息是正确的，并根据这个信息更新 数据库中的公交线路数据，否则JYY会无视这个错误信息； 2)  对于del和change信息，如果站点x和站点y之间有公交车直接运营， JYY 则认为这条信息是正确的，并更新数据库，否则 JYY 则会无视这个错误 信息； 3)  对于dest 信息，如果站点x不能到达站点 y，JYY也会认为这一条询问信 息是错误的。 JYY希望你能够帮助他完成这一个公交信息应用。

输入格式

输入数据的第一行包含两个整数 N 和Q。 接下来 Q行，每行对应一个 JYY需要处理的信息。 在收到第一条信息之前，没有任何公交车在运营。

输出格式

输出 Q行，每行都对应一个输入文件中的信息，具体内容如下： 1)  如果输入的信息是错误的，输出“ERROR”； 2)  对于一个正确的 add，del，change信息，输出“OK”； 3)  对于一个正确的 dest 信息，输出一行两个整数，分别为终点站的编号和 开到终点站所需要的时间； 4)  对于reach 信息，如果用户询问的两个公交站点相互可达，输出“YES”， 否则输出“NO”。 注意：输入输出数据很大，请使用快速的输入输出方式。

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

ERROR
OK
OK
NO
ERROR
ERROR
OK
3 1
5 6
 

提示

2 < =  N < =  10^5 ,2 < =  Q < =  2×10^5，任意信息均保证X≠Y， 1 < = X,Y<=N,1 <=Z<=10^4。

题目来源

By 佚名上传