codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.