这是一个交互式问题。
Vlad 有一个包含 $n$ 个顶点的空有向图,顶点编号为 $1$ 到 $n$。他计划逐一向该图中添加 $n - 1$ 条有向边,并确保在任何时刻都满足以下两个条件:
- 该图是一个有向森林:每个连通分量都是一棵有向有根树的形式,其中边的方向是从根节点指向叶子节点。
- 对于图中的每个顶点,从该顶点可达的顶点集合是一个连续的整数区间(即中间没有空隙)。
你的任务是在每次添加边后检查这两个条件是否满足。
交互协议
首先,评测程序将提供一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$),表示顶点数。
接下来,将进行 $n - 1$ 次加边操作。对于每次操作,评测程序将输入两个顶点编号 $v$ 和 $u$ ($1 \le v, u \le n; v \ne u$)。请检查在添加有向边 $v \to u$ 后是否满足 Vlad 的条件,并在单独的一行中按以下格式输出答案:
- 如果不满足第一个条件,输出字符串
"Bad oriented forest"。 - 如果不满足第二个条件,输出字符串
"Bad segment at v",其中 $v$ 是任意一个不满足该条件的顶点编号。 - 如果两个条件都不满足,输出上述两条消息中的任意一条。
- 否则,如果两个条件都满足,输出字符串
"Good"。
如果任何一个条件不满足,你的程序在输出相应的消息后应立即终止,即使处理的边数少于 $n - 1$ 条。
不会重复添加相同的有向边 $v \to u$。所有 $n - 1$ 次加边操作都是预先确定的。
样例
输入样例 1
6 1 2 3 4 3 1 5 6 5 1
输出样例 1
Good Good Good Good Bad segment at 5