You are given two simple undirected graphs $$$F$$$ and $$$G$$$ with $$$n$$$ vertices. $$$F$$$ has $$$m_1$$$ edges while $$$G$$$ has $$$m_2$$$ edges. You may perform one of the following two types of operations any number of times:

Select two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq n$$$) such that there is an edge between $$$u$$$ and $$$v$$$ in $$$F$$$. Then, remove that edge from $$$F$$$.
Select two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq n$$$) such that there is no edge between $$$u$$$ and $$$v$$$ in $$$F$$$. Then, add an edge between $$$u$$$ and $$$v$$$ in $$$F$$$.

Determine the minimum number of operations required such that for all integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq n$$$), there is a path from $$$u$$$ to $$$v$$$ in $$$F$$$ if and only if there is a path from $$$u$$$ to $$$v$$$ in $$$G$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of independent test cases.

The first line of each test case contains three integers $$$n$$$, $$$m_1$$$, and $$$m_2$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$, $$$0 \leq m_1,m_2 \leq 2\cdot 10^5$$$) — the number of vertices, the number of edges in $$$F$$$, and the number of edges in $$$G$$$.

The following $$$m_1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v\leq n$$$) — there is an edge between $$$u$$$ and $$$v$$$ in $$$F$$$. It is guaranteed that there are no repeated edges or self loops.

The following $$$m_2$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v\leq n$$$) — there is an edge between $$$u$$$ and $$$v$$$ in $$$G$$$. It is guaranteed that there are no repeated edges or self loops.

It is guaranteed that the sum of $$$n$$$, the sum of $$$m_1$$$, and the sum of $$$m_2$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer denoting the minimum operations required on a new line.

Note

In the first test case you can perform the following three operations:

Add an edge between vertex $$$1$$$ and vertex $$$3$$$.
Remove the edge between vertex $$$1$$$ and vertex $$$2$$$.
Remove the edge between vertex $$$2$$$ and vertex $$$3$$$.

It can be shown that fewer operations cannot be achieved.

In the second test case, $$$F$$$ and $$$G$$$ already fulfill the condition in the beginning.

In the fifth test case, the edges from $$$1$$$ to $$$3$$$ and from $$$2$$$ to $$$3$$$ must both be removed.

Graph Composition

Examples