#358. 传递性

传统 2000 ms 256 MiB
标准 IO
文本比较 admin 标签

题目描述

给定nn个点的无向图,qq组询问,需要支持以下两种操作:

  • 1 x y1 \ x \ y: 如果存在边(x,y)(x, y),则删除边(x,y)(x, y),否则加入边(x,y)(x, y)

  • 2 x y2 \ x \ y:查询是否存在一条边(a,b)(a, b),使得a[min(x,y),max(x,y)]a \in [min(x, y), max(x, y)]并且b[min(x,y),max(x,y)]b \notin [min(x, y), max(x, y)]

输入格式

第一行给出n(1n106),q(1q106)n(1 \leq n \leq 10^6), q (1 \leq q \leq 10^6)

接下来qq行,每行给出三个数op(1op2),x(1an),y(1bn)op(1 \leq op \leq 2), x(1 \leq a \leq n), y(1 \leq b \leq n),含义如题意所示

输出格式

对于每次操作2,如果存在一条边满足题意,输出 yami,否则输出 god(区分大小写,不含引号)。

注意:输出不要有多余的空格,文末不要有多余的回车。

样例

样例输入

5 5
2 1 5
1 1 2
2 1 1
2 1 2
2 1 5

样例输出

god
yami
god
god