1717  Multisets
Time Limit : 4 Second
Memory Limit : 256 MB
Submission: 10
Solved: 3
 Description
Give you a sequence A of length N. There are N multisets initially, the i^{th} multiset is {A_{i}}.
And then there are M operations. In each operation, give you j and k. let S be the multiset A_{j} belongs to, T be the multiset A_{k} belongs to. You have to answer how many pairs (a, b) satisfying: a ∈ S, b ∈ T and a > b, and then merge S and T.
 Input
The first line of the input gives the number of test cases T. T test cases follow.
Each test case starts with a line consist of two integers N and M. The next line consists of N integers A_{i} indicating the i^{th} element in the sequence. Then M lines follow. Each line consists of two integers j and k.
1 ≤ N, M ≤ 10^{5}_{.}
A_{i} is representable by 32bit signed integer.
1 ≤ j, k ≤ N for every operation.
1 ≤ T × (N + M) ≤ 4×10^{5}.
 Output
For each test case, first output one line containing “Case x:”, where x is the test case number.
Then for every operation, output one line consists of one integer indicating the number of pairs (a, b) described above or 1 if A_{j} and A_{k} belongs to a same multiset.
 sample input

2 5 3 1 2 3 4 5 1 2 3 2 1 3 4 4 0 0 1 1 1 2 4 3 3 2 1 4
 sample output

Case #1: 0 2 1 Case #2: 0 0 4 1
 hint
 source
 lizhen