Week7: merging tables

[chaicko]

Problem Introduction

In this problem, your goal is to simulate a sequence of merge operations with tables in a database.

Problem Description

Task

There are n tables stored in some database. The tables are numbered from 1 to n. All tables share the same set of columns. Each table contains either several rows with real data or a symbolic link to another table. Initially, all tables contain data, and i-th table has r_i rows. You need to perform m of the following operations:

1. Consider table number destination_i . Traverse the path of symbolic links to get to the data. That
   is,
   while destination_i contains a symbolic link instead of real data do destination_i ← symlink(destination_i)
2. Consider the table number source_i and traverse the path of symbolic links from it in the same
   manner as for destination_i.
3. Now, destination_i and source_i are the numbers of two tables with real data. If destination_i != source_i , copy all the rows from table source_i to table destination_i , then clear the table source_i and instead of real data put a symbolic link to destination_i into it.
4. Print the maximum size among all n tables (recall that size is the number of rows in the table). If the table contains only a symbolic link, its size is considered to be 0.

See examples and explanations for further clarifications.

Input Format

The first line of the input contains two integers n and m — the number of tables in the database and the number of merge queries to perform, respectively.
The second line of the input contains n integers r_i — the number of rows in the i-th table.
Then follow m lines describing merge queries. Each of them contains two integers destination_i and source_i — the numbers of the tables to merge.

Constraints

1 ≤ n, m ≤ 100 000; 0 ≤ r_i ≤ 10 000; 1 ≤ destination_i , source_i ≤ n.

Output Format

For each query print a line containing a single integer — the maximum of the sizes of all
tables (in terms of the number of rows) after the corresponding operation.

Time Limits

C: 2 sec, C++: 2 sec, Java: 14 sec, Python: 6 sec. C#: 3 sec, Haskell: 4 sec, JavaScript: 6 sec, Ruby: 6 sec, Scala: 14 sec.

Memory Limit

512Mb.