logo AlgoBeat OnlineJudge
登录 注册

#103880. [BZOJ 3880] 炼辰

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目背景

载着荣耀的流光在星云上启程,不知终落谁手。

星云由 颗星组成,呈环状分布(按照顺时针方向标号顺序为 ),流光可以有两种流动方式:

  1. 沿顺时针由一颗星滑向它的下一颗星。
  2. 我们定义「焱」为一种传送机制,即若两个星球之间燃烧着「焱」,则顺时针序靠后的星球,可以通过此机制传送回顺时针序靠前的那个星球。

某一天星云被破坏了,只剩下了最后一抹荣耀流光被两股神秘力量角逐。而破坏带来了两个限制:

  1. 某颗行星 被设定为流光禁区(即永远无法被选择为流光的落脚点)。
  2. 一旦一颗星被流光划过,那么就再也不能被经过了。

现在两种神秘力量轮流引导流光的流动,先手在第一次操作时为确定流光的起始位置,问谁可以拿到最后一次的掌控权来获得胜利?

另外学者们发现,「焱」具有特殊的性质:

如果把每个「焱」视为零点为其两个星球的类似圆弧的轨迹,那么两条轨迹之间不会相交或外切,但是内切和包含以及相离都是合法的。

输入格式

第一行三个整数 表示星云上 个点按标号顺时针环形排列,有 个「焱」,行星 为流光禁区。

接下来有 行,每行两个整数 ,表示 之间存在一个「焱」。

输出格式

如果先手胜,输出 dawn,否则输出 galaxy

样例

样例输入 #1

5 5 3
1 1
1 4
2 3
3 4
4 5

样例输出 #1

dawn

数据范围与提示

对于 的数据,

By YGY