# 描述

Presumably, you all have known the question of stable marriage match. A girl will choose a boy; it is similar as the game of playing house we used to play when we are kids. What a happy time as so many friends playing together. And it is normal that a fight or a quarrel breaks out, but we will still play together after that, because we are kids.
Now, there are $2n$ kids, $n$ boys numbered from $1$ to $n$, and $n$ girls numbered from $1$ to $n$. you know, ladies first. So, every girl can choose a boy first, with whom she has not quarreled, to make up a family. Besides, the girl $X$ can also choose boy $Z$ to be her boyfriend when her friend, girl $Y$ has not quarreled with him. Furthermore, the friendship is mutual, which means $a$ and $c$ are friends provided that $a$ and $b$ are friends and $b$ and $c$ are friend.
Once every girl finds their boyfriends they will start a new round of this game—marriage match. At the end of each round, every girl will start to find a new boyfriend, who she has not chosen before. So the game goes on and on.
Now, here is the question for you, how many rounds can these $2n$ kids totally play this game?

## Input

There are several test cases. First is a integer $T$, means the number of test cases.
Each test case starts with three integer $n, m$ and $f$ in a line $(3≤n≤100,0<m<n*n,0≤f<n)$. $n$ means there are $2 \times n$ children, $n$ girls(number from $1$ to $n$) and $n$ boys(number from $1$ to $n$).
Then $m$ lines follow. Each line contains two numbers $a$ and $b$, means girl $a$ and boy $b$ had never quarreled with each other.
Then $f$ lines follow. Each line contains two numbers $c$ and $d$, means girl $c$ and girl $d$ are good friends.

## Output

For each case, output a number in one line. The maximal number of Marriage Match the children can play.

# 思路

• 由于女孩之间的朋友具有传递关系，所以我们先用floyd对女孩之间的朋友关系图传递闭包，从而得出每个女孩的备选男孩。
• 我们要求游戏最多可以进行几轮，可以考虑二分答案，假设答案为$mid$。建图方式如下：
• 女孩编号：$0 \sim n-1$；
• 男孩编号：$n \sim 2n-1$；
• 超级源点：$2n$；
• 超级汇点：$2n+1$；
• 超级源点→女孩：容量为$mid$；
• 男孩→超级汇点：容量为$mid$；
• 女孩→其可选的男孩：容量为$1$。
• 若上图跑出的最大流为$mid \times n$，则说明当前答案可行，L=mid+1，否则R=mid-1
• 本题还可以用二分图匹配来做，即首先建立女孩与男孩的二分图,并且连好可能的边. 然后进行一轮匹配,如果此时有完美匹配,那么就删除这些匹配边,进行第二轮匹配,如果还有完美匹配，就继续……

0%