稳定婚姻

题目描述

已知 $n$ 对夫妻。第 $i$ 对夫妻的男方记为 $B_i$，女方记为 $G_i$。如果男方 $B_i$ 与女方 $G_j$ 曾经交往过，其中 $i\ne j$，那么婚姻关系发生变化时，他们可能重新结合并引起一连串配对变化。

如果在第 $i$ 对夫妻离婚的前提下，这 $2n$ 个人最终仍能重新组成 $n$ 对情侣，则称婚姻 $i$ 为不安全；否则称婚姻 $i$ 为安全。

请判断每对婚姻是否安全。

输入格式

第一行包含一个正整数 $n$，表示夫妻对数。

接下来 $n$ 行，每行包含两个字符串，依次表示一对夫妻中女方和男方的姓名。

下一行包含一个非负整数 $m$，表示曾经交往过的情侣对数。

接下来 $m$ 行，每行包含两个字符串，依次表示女方和男方的姓名。

输出格式

输出 $n$ 行。第 $i$ 行输出 Safe 表示婚姻 $i$ 安全，或输出 Unsafe 表示婚姻 $i$ 不安全。

样例输入 1

2
Melanie Ashley
Scarlett Charles
1
Scarlett Ashley

样例输出 1

Safe
Safe

样例输入 2

2
Melanie Ashley
Scarlett Charles
2
Scarlett Ashley
Melanie Charles

样例输出 2

Unsafe
Unsafe

数据范围

所有姓名只包含英文大小写字母，大小写敏感，长度不超过 $8$。每对关系只出现一次，关系中的姓名均已在夫妻名单中出现，所有 $2n$ 个人的姓名互不相同。

$1\le n\le 4000$，$0\le m\le 20000$。