题目描述

已知 $n$ 对夫妻的结合情况,记第 $i$ 对夫妻中丈夫为 $B_i$,妻子为 $G_i$。假如某位丈夫 $B_i$ 和另一位妻子 $G_j$ 在过去曾经有过一段恋情($i \neq j$),那么一旦某一方和自己配偶的感情出现裂痕,就可能引发一场连锁风波。设想 $B_i$ 与妻子 $G_i$ 感情破裂,于是 $B_i$ 与旧相识 $G_j$ 重新走到一起,而被抛下的 $B_j$ 心有不甘,又联系上了自己从前的恋人 $G_k$ ……分离与重组就像推倒的多米诺骨牌一样接连发生。如果在 $B_i$ 与 $G_i$ 分开的前提下,这 $2n$ 个人最终仍然能够重新配成 $n$ 对伴侣,就称第 $i$ 段婚姻是不稳定的,否则称它是稳固的。

给出所有需要的信息,请你判断每段婚姻是否稳固。

输入格式

第一行为一个正整数 $n$,表示夫妻的对数；

以下 $n$ 行,每行包含两个字符串,表示这 $n$ 对夫妻的姓名（先女后男）,由一个空格隔开；

第 $n+2$ 行包含一个正整数 $m$,表示曾经相互喜欢过的情侣对数；

以下 $m$ 行,每行包含两个字符串,表示这 $m$ 对相互喜欢过的情侣姓名（先女后男）,由一个空格隔开。

输出格式

输出文件共包含 $n$ 行,第 $i$ 行为 Safe（如果婚姻 $i$ 是稳固的）或 Unsafe（如果婚姻 $i$ 是不稳定的）。

样例

2
Melanie Ashley
Scarlett Charles
1
Scarlett Ashley

Safe
Safe

2
Melanie Ashley
Scarlett Charles
2
Scarlett Ashley
Melanie Charles

Unsafe
Unsafe

提示

对于 $20\%$ 的数据,$n \le 20$；

对于 $40\%$ 的数据,$n \le 100$,$m \le 400$；

对于 $100\%$ 的数据,所有姓名字符串中只包含英文大小写字母,大小写敏感,长度不大于 $8$,保证每对关系只在输入文件中出现一次,输入文件的最后 $m$ 行不会出现未在之前出现过的姓名,这 $2n$ 个人的姓名各不相同,$1 \le n \le 4000$,$0 \le m \le 20000$。