2060E.md (2514B)
1 Source: https://codeforces.com/problemset/problem/2060/E 2 3 E. Graph Composition 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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: 22 23 * 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$. 24 * 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$. 25 26 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$. 27 28 Input 29 30 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of independent test cases. 31 32 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$. 33 34 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. 35 36 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. 37 38 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$. 39 40 Output 41 42 For each test case, output a single integer denoting the minimum operations required on a new line. 43 44 Example 45 46 Input 47 48 ``` 49 5 50 51 3 2 1 52 53 1 2 54 55 2 3 56 57 1 3 58 59 2 1 1 60 61 1 2 62 63 1 2 64 65 3 2 0 66 67 3 2 68 69 1 2 70 71 1 0 0 72 73 3 3 1 74 75 1 2 76 77 1 3 78 79 2 3 80 81 1 2 82 ``` 83 84 Output 85 86 ``` 87 3 88 0 89 2 90 0 91 2 92 ``` 93 94 Note 95 96 In the first test case you can perform the following three operations: 97 98 1. Add an edge between vertex $1$ and vertex $3$. 99 2. Remove the edge between vertex $1$ and vertex $2$. 100 3. Remove the edge between vertex $2$ and vertex $3$. 101 102 It can be shown that fewer operations cannot be achieved. 103 104 In the second test case, $F$ and $G$ already fulfill the condition in the beginning. 105 106 In the fifth test case, the edges from $1$ to $3$ and from $2$ to $3$ must both be removed.