Stable Marriage

Problem Source

BZOJ 2140

Problem Description

We know the marital status of $n$ couples. Call the husband of the $i$-th couple $B_i$ and the wife $G_i$. If some man $B_i$ and some woman $G_j$ have ever been in a relationship (whether in university, high school, or even kindergarten, with $i \le j$), then when either of them has trouble with their spouse (i.e. $B_i$ with $G_i$, or $B_j$ with $G_j$), there is a possibility that they run away together. Suppose $B_i$ and his spouse $G_i$ fall out of love; then $B_i$ and $G_j$ rekindle their old flame, and in turn $B_j$, feeling cuckolded, contacts his first love $G_k$... a chain of divorces unfolds like falling dominoes. If, under the premise that $B_i$ and $G_i$ divorce, these $2n$ people can still end up paired into $n$ couples, then marriage $i$ is called unsafe; otherwise it is safe.

Given the required information, your task is to judge whether each marriage is safe.

Input Format

The first line is a positive integer $n$, the number of couples.

The next $n$ lines each contain two strings, the names of the $n$ couples (wife first, then husband), separated by a space.

The $(n+2)$-th line contains a positive integer $m$, the number of pairs who have ever liked each other.

The next $m$ lines each contain two strings, the names of those $m$ pairs who have ever liked each other (wife first, then husband), separated by a space.

For all data: every name consists only of English letters (case-sensitive), with length at most $8$; each relationship appears at most once in the input; the last $m$ lines will not introduce any name not seen before; the $2n$ people all have distinct names; $1 \le n \le 4000$, $0 \le m \le 20000$.

Output Format

The output contains $n$ lines; the $i$-th line is Safe if marriage $i$ is safe, or Unsafe if it is unsafe.

Sample Input 1

2
Melanie Ashley
Scarlett Charles
1
Scarlett Ashley

Sample Output 1

Safe
Safe

Sample Input 2

2
Melanie Ashley
Scarlett Charles
2
Scarlett Ashley
Melanie Charles

Sample Output 2

Unsafe
Unsafe