题目描述

小青和小智发现了一棵苹果树。这棵苹果树可以看作一棵有 $n$ 个节点的无根树，每个节点上都有一个苹果。

游戏开始前，裁判会先摘下编号为 $s$ 的节点上的苹果。随后，小青和小智轮流进行操作，小青先手。

每次操作时，当前玩家必须摘下一个满足以下条件的苹果：

• 该苹果所在节点与上一次被摘下苹果所在节点相邻；
• 该苹果尚未被摘下。

每个节点上的苹果最多只能被摘下一次。

当轮到某一方操作时，若其无法摘下任何满足条件的苹果，则该玩家输掉游戏，另一名玩家获胜。

假设小青和小智都采取最优策略，请你判断最终谁会获胜。

输入格式

第一行包含一个整数 $n$，表示苹果树的节点数。

接下来 $n-1$ 行，每行包含两个整数 $u, v$，表示节点 $u$ 与节点 $v$ 之间有一条边。

最后一行包含一个整数 $s$，表示裁判最开始摘下苹果的节点编号。

输出格式

输出一行一个字符串：

• 若小青获胜，输出 Qing；
• 若小智获胜，输出 Zhi。

数据范围

对于所有测试数据，满足：

$1 \le n \le 10^5$

$1 \le u, v \le n$

$1 \le s \le n$

保证输入的 $n-1$ 条边构成一棵树。

输入输出样例 #1

输入

4
1 2
2 3
3 4
2

输出

Qing

样例解释

裁判首先摘下节点 $2$ 上的苹果。

此时小青可以选择摘下节点 $1$ 或节点 $3$ 上的苹果。

若小青摘下节点 $1$ 上的苹果，则上一次被摘下的苹果位于节点 $1$。节点 $1$ 只与节点 $2$ 相邻，而节点 $2$ 上的苹果已经被摘下，因此小智无法进行操作，小智输掉游戏。

因此，在最优策略下，小青会选择节点 $1$，最终小青获胜。

输入输出样例 #2

输入

5
1 2
2 3
3 4
4 5
3

输出

Zhi

样例解释

裁判首先摘下节点 $3$ 上的苹果。

若小青摘下节点 $2$，则小智会摘下节点 $1$，之后小青无法操作。

若小青摘下节点 $4$，则小智会摘下节点 $5$，之后小青无法操作。

无论小青如何选择，小智都能获胜，因此答案为 Zhi。