P1407 [National Training Team] Stable Marriage

We know the marital status of $n$ couples. Denote the man of the $i$-th couple as $B_i$ and the woman as $G_i$. If some man $B_i$ and some woman $G_j$ once dated (whether in college, high school, or even kindergarten, with $i \neq j$), then when either party has problems with his or her spouse (that is, $B_i$ with $G_i$ or $B_j$ with $G_j$), they may elope. Suppose $B_i$ and his spouse $G_i$ do not get along, then $B_i$ and $G_j$ rekindle their relationship, and then $B_j$, feeling upset after being cheated on, contacts his first love $G_k$... A chain of divorces follows like dominoes. If, under the premise that $B_i$ and $G_i$ divorce, these $2n$ people can still eventually be paired into $n$ couples, then we call marriage $i$ unsafe; otherwise, marriage $i$ is safe. Given the required information, your task is to determine whether each marriage is safe.

The first line contains a positive integer $n$, the number of couples. Each of the following $n$ lines contains two strings, the names of these $n$ couples (female first, then male), separated by a space. The $n+2$-th line contains a positive integer $m$, the number of couples who once dated each other. Each of the following $m$ lines contains two strings, the names of these $m$ couples who once dated each other (female first, then male), separated by a space.

The output contains $n$ lines. The $i$-th line is `Safe` (if marriage $i$ is safe) or `Unsafe` (if marriage $i$ is unsafe).

For $20\%$ of the testdata, $n \le 20$. For $40\%$ of the testdata, $n \le 100$, $m \le 400$. For $100\%$ of the testdata, all name strings contain only English letters, are case-sensitive, and have length no greater than $8$. Each relationship appears only once in the input. The last $m$ lines of the input file will not contain any names that did not appear before. All $2n$ names are distinct. $1 \le n \le 4000$, $0 \le m \le 20000$. Translated by ChatGPT 5