Task. There are tables stored in some database. The tables are numbered from 1 to . 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 -th table has rows. You need to perform of

the following operations:

1. Consider table number . Traverse the path of symbolic links to get to the data. That is,

while contains a symbolic link instead of real data do

symlink()

2. Consider the table number and traverse the path of symbolic links from it in the same

manner as for .

3. Now, and are the numbers of two tables with real data. If =

, copy all the rows from table to table , then clear the table

and instead of real data put a symbolic link to into it.

4. Print the maximum size among all 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 and the number of tables in the

database and the number of merge queries to perform, respectively.

The second line of the input contains integers the number of rows in the -th table.

Then follow lines describing merge queries. Each of them contains two integers and

the numbers of the tables to merge.

Constraints. 1 , 100 000; 0 10 000; 1 , .

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.

Sample 1.

Input:

5 5

1 1 1 1 1

3 5

2 4

1 4

5 4

5 3

Output:

2

2

3

5

5

In this sample, all the tables initially have exactly 1 row of data. Consider the merging operations:

1. All the data from the table 5 is copied to table number 3. Table 5 now contains only a symbolic

link to table 3, while table 3 has 2 rows. 2 becomes the new maximum size.

2. 2 and 4 are merged in the same way as 3 and 5.

3. We are trying to merge 1 and 4, but 4 has a symbolic link pointing to 2, so we actually copy

all the data from the table number 2 to the table number 1, clear the table number 2 and put a

symbolic link to the table number 1 in it. Table 1 now has 3 rows of data, and 3 becomes the new

maximum size.

4. Traversing the path of symbolic links from 4 we have 4 2 1, and the path from 5 is 5 3.

So we are actually merging tables 3 and 1. We copy all the rows from the table number 1 into the

table number 3, and now the table number 3 has 5 rows of data, which is the new maximum.

5. All tables now directly or indirectly point to table 3, so all other merges wont change anything.

Sample 2.

Input:

6 4

10 0 5 0 3 3

6 6

6 5

5 4

4 3

Output:

10

10

10

11

Explanation:

In this example tables have different sizes. Let us consider the operations:

1. Merging the table number 6 with itself doesnt change anything, and the maximum size is 10

(table number 1).

2. After merging the table number 5 into the table number 6, the table number 5 is cleared and has

size 0, while the table number 6 has size 6. Still, the maximum size is 10.

3. By merging the table number 4 into the table number 5, we actually merge the table number 4

into the table number 6 (table 5 now contains just a symbolic link to table 6), so the table number

4 is cleared and has size 0, while the table number 6 has size 6. Still, the maximum size is 10.

4. By merging the table number 3 into the table number 4, we actually merge the table number 3

into the table number 6 (table 4 now contains just a symbolic link to table 6), so the table number

3 is cleared and has size 0, while the table number 6 has size 11, which is the new maximum size.

***********SOURCE CODE*******

#include

#include

#include

#include

#include

using std::cin;

using std::cout;

using std::endl;

using std::max;

using std::vector;

struct DisjointSetsElement {

int size, parent, rank;

DisjointSetsElement(int size = 0, int parent = -1, int rank = 0):

size(size), parent(parent), rank(rank) {}

};

struct DisjointSets {

int size;

int max_table_size;

vector sets;

DisjointSets(int size): size(size), max_table_size(0), sets(size) {

for (int i = 0; i < size; i++)

sets[i].parent = i;

}

int getParent(int table) {

// find parent and compress path

}

void merge(int destination, int source) {

int realDestination = getParent(destination);

int realSource = getParent(source);

if (realDestination != realSource) {

// merge two components

// use union by rank heuristic

// update max_table_size

}

}

};

int main() {

int n, m;

cin >> n >> m;

DisjointSets tables(n);

for (auto &table : tables.sets) {

cin >> table.size;

tables.max_table_size = max(tables.max_table_size, table.size);

}

for (int i = 0; i < m; i++) {

int destination, source;

cin >> destination >> source;

--destination;

--source;

tables.merge(destination, source);

cout << tables.max_table_size << endl;

}

return 0;

}