# 【CodeForces Contest 1012】题解

Posted on

### A. Photo of The Sky

#### Statement

There is a beautiful garden of stones in Innopolis.

Its most beautiful place is the n piles with stones numbered from $n$.

EJOI participants have visited this place twice.

When they first visited it, the number of stones in piles was $x_1, x_2, ldots, x_n$, correspondingly. One of the participants wrote down this sequence in a notebook.

They visited it again the following day, and the number of stones in piles was equal to $y_1, y_2, ldots, y_n$. One of the participants also wrote it down in a notebook.

It is well known that every member of the EJOI jury during the night either sits in the room $108$ or comes to the place with stones. Each jury member who comes there either takes one stone for himself or moves one stone from one pile to another. We can assume that there is an unlimited number of jury members. No one except the jury goes to the place with stones at night.

Participants want to know whether their notes can be correct or they are sure to have made a mistake.

#### I/O

##### Input

The first line of the input file contains a single integer $n$, the number of piles with stones in the garden $1 leq n leq 50$.

The second line contains n integers separated by spaces $x_1, x_2, ldots, x_n$, the number of stones in piles recorded in the notebook when the participants came to the place with stones for the first time ($0 leq x_i leq 1000$).

The third line contains $n$ integers separated by spaces $y_1, y_2, ldots, y_n$, the number of stones in piles recorded in the notebook when the participants came to the place with stones for the second time ($0 leq y_i leq 1000$).

##### Output

If the records can be consistent output “Yes”, otherwise output “No” (quotes for clarity).

### B. Chemical table

#### Statement

Innopolis University scientists continue to investigate the periodic table. There are n·m known elements and they form a periodic table: a rectangle with n rows and m columns. Each element can be described by its coordinates (r, c) (1 ≤ r ≤ n, 1 ≤ c ≤ m) in the table.

Recently scientists discovered that for every four different elements in this table that form a rectangle with sides parallel to the sides of the table, if they have samples of three of the four elements, they can produce a sample of the fourth element using nuclear fusion. So if we have elements in positions (r1, c1), (r1, c2), (r2, c1), where r1 ≠ r2 and c1 ≠ c2, then we can produce element (r2, c2).

Samples used in fusion are not wasted and can be used again in future fusions. Newly crafted elements also can be used in future fusions.

Innopolis University scientists already have samples of q elements. They want to obtain samples of all n·m elements. To achieve that, they will purchase some samples from other laboratories and then produce all remaining elements using an arbitrary number of nuclear fusions in some order. Help them to find the minimal number of elements they need to purchase.

#### I/O

##### Input

The first line contains three integers n, m, q (1 ≤ n, m ≤ 200 000; 0 ≤ q ≤ min(n·m, 200 000)), the chemical table dimensions and the number of elements scientists already have.

The following q lines contain two integers ri, ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m), each describes an element that scientists already have. All elements in the input are different.

##### Output

Print the minimal number of elements to be purchased.

#### Sample

##### Note

There are several possible solutions. One of them is illustrated below.

Note that after purchasing one element marked as red it’s still not possible to immidiately produce the middle element in the bottom row (marked as 4). So we produce the element in the left-top corner first (marked as 1), and then use it in future fusions.