実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
長さ N の数列 A = (A_1, A_2, \dots, A_N) が与えられます。
あなたは次の操作をちょうど K 回行います。
- A の先頭の要素を取り除き、A の末尾に 0 を挿入する。
操作を行った後の A の要素をすべて出力してください。
制約
- 1 \leq N \leq 100
- 1 \leq K \leq 100
- 1 \leq A_i \leq 100
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_N
出力
操作を行った後の A の要素を空白区切りで 1 行に出力せよ。
入力例 1
3 2 2 7 8
出力例 1
8 0 0
操作を行う前は A = (2, 7, 8) です。
操作を 1 回行った時点では A = (7, 8, 0) です。
操作を 2 回行った時点では A = (8, 0, 0) です。
よって (8, 0, 0) が答えです。
入力例 2
3 4 9 9 9
出力例 2
0 0 0
入力例 3
9 5 1 2 3 4 5 6 7 8 9
出力例 3
6 7 8 9 0 0 0 0 0
Score : 100 points
Problem Statement
You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.
You perform the following operation exactly K times:
- remove the initial element of A and append a 0 to the tail of A.
Print all the elements of A after the operations.
Constraints
- 1 \leq N \leq 100
- 1 \leq K \leq 100
- 1 \leq A_i \leq 100
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the elements of A after the operations in one line, separated by spaces.
Sample Input 1
3 2 2 7 8
Sample Output 1
8 0 0
Before the operations, A = (2, 7, 8).
After performing the operation once, A = (7, 8, 0).
After performing the operation twice, A = (8, 0, 0).
Thus, (8, 0, 0) is the answer.
Sample Input 2
3 4 9 9 9
Sample Output 2
0 0 0
Sample Input 3
9 5 1 2 3 4 5 6 7 8 9
Sample Output 3
6 7 8 9 0 0 0 0 0
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
関数 f を f(x) = x^2 + 2x + 3 と定義します。
整数 t が入力されるので、 f(f(f(t)+t)+f(f(t))) を求めてください。
ただし、答えは 2 \times 10^9 以下の整数であることが保証されます。
制約
- t は 0 以上 10 以下の整数である
入力
入力は以下の形式で標準入力から与えられる。
t
出力
答えを整数として出力せよ。
入力例 1
0
出力例 1
1371
答えは以下の手順によって計算されます。
- f(t) = t^2 + 2t + 3 = 0 \times 0 + 2 \times 0 + 3 = 3
- f(t)+t = 3 + 0 = 3
- f(f(t)+t) = f(3) = 3 \times 3 + 2 \times 3 + 3 = 18
- f(f(t)) = f(3) = 18
- f(f(f(t)+t)+f(f(t))) = f(18+18) = f(36) = 36 \times 36 + 2 \times 36 + 3 = 1371
入力例 2
3
出力例 2
722502
入力例 3
10
出力例 3
1111355571
Score : 100 points
Problem Statement
Let us define a function f as f(x) = x^2 + 2x + 3.
Given an integer t, find f(f(f(t)+t)+f(f(t))).
Here, it is guaranteed that the answer is an integer not greater than 2 \times 10^9.
Constraints
- t is an integer between 0 and 10 (inclusive).
Input
Input is given from Standard Input in the following format:
t
Output
Print the answer as an integer.
Sample Input 1
0
Sample Output 1
1371
The answer is computed as follows.
- f(t) = t^2 + 2t + 3 = 0 \times 0 + 2 \times 0 + 3 = 3
- f(t)+t = 3 + 0 = 3
- f(f(t)+t) = f(3) = 3 \times 3 + 2 \times 3 + 3 = 18
- f(f(t)) = f(3) = 18
- f(f(f(t)+t)+f(f(t))) = f(18+18) = f(36) = 36 \times 36 + 2 \times 36 + 3 = 1371
Sample Input 2
3
Sample Output 2
722502
Sample Input 3
10
Sample Output 3
1111355571
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
N 個の駅、駅 1, 駅 2, \ldots, 駅 N が直線上にこの順に並んでいます。
ここで、1\leq i\leq N-1 について、駅 i と駅 (i+1) の間の距離は D_i です。
1\leq i<j\leq N をみたす整数の組 (i,j) それぞれについて、駅 i と駅 j の間の距離を求めてください。
なお、出力形式については出力の欄を参照してください。
制約
- 2 \leq N \leq 50
- 1 \leq D_i \leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
D_1 D_2 \ldots D_{N-1}
出力
N-1 行出力せよ。
i 行目 (1\leq i\leq N-1) には、(N-i) 個の整数を空白区切りで出力せよ。
i 行目の j 番目 (1\leq j\leq N-i) には、駅 i と駅 (i+j) の間の距離を出力せよ。
入力例 1
5 5 10 2 3
出力例 1
5 15 17 20 10 12 15 2 5 3
各駅の間の距離は次のようになります。
- 駅 1 と駅 2 の間の距離は 5 です。
- 駅 1 と駅 3 の間の距離は 5+10=15 です。
- 駅 1 と駅 4 の間の距離は 5+10+2=17 です。
- 駅 1 と駅 5 の間の距離は 5+10+2+3=20 です。
- 駅 2 と駅 3 の間の距離は 10 です。
- 駅 2 と駅 4 の間の距離は 10+2=12 です。
- 駅 2 と駅 5 の間の距離は 10+2+3=15 です。
- 駅 3 と駅 4 の間の距離は 2 です。
- 駅 3 と駅 5 の間の距離は 2+3=5 です。
- 駅 4 と駅 5 の間の距離は 3 です。
よって、上記のように出力します。
入力例 2
2 100
出力例 2
100
Score : 200 points
Problem Statement
There are N stations, station 1, station 2, \ldots, station N, arranged in this order on a straight line.
Here, for 1\leq i\leq N-1, the distance between stations i and (i+1) is D_i.
For each pair of integers (i,j) satisfying 1\leq i<j\leq N, find the distance between stations i and j.
For the output format, refer to the Output section.
Constraints
- 2 \leq N \leq 50
- 1 \leq D_i \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
D_1 D_2 \ldots D_{N-1}
Output
Output N-1 lines.
On the i-th line (1\leq i\leq N-1), output (N-i) integers, separated by spaces.
The j-th integer on the i-th line (1\leq j\leq N-i) should be the distance between stations i and (i+j).
Sample Input 1
5 5 10 2 3
Sample Output 1
5 15 17 20 10 12 15 2 5 3
The distances between stations are as follows:
- The distance between stations 1 and 2 is 5.
- The distance between stations 1 and 3 is 5+10=15.
- The distance between stations 1 and 4 is 5+10+2=17.
- The distance between stations 1 and 5 is 5+10+2+3=20.
- The distance between stations 2 and 3 is 10.
- The distance between stations 2 and 4 is 10+2=12.
- The distance between stations 2 and 5 is 10+2+3=15.
- The distance between stations 3 and 4 is 2.
- The distance between stations 3 and 5 is 2+3=5.
- The distance between stations 4 and 5 is 3.
Thus, output as shown above.
Sample Input 2
2 100
Sample Output 2
100
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
高橋君は改札機の利用履歴を集計しました。 しかし、高橋君はうっかりいくつかの入退場記録を消してしまいました。 高橋君は消してしまった記録の復元を試みようとしています。
i, o のみからなる文字列 S が与えられます。
S の任意の位置に文字を 0 文字以上挿入することで、変更後の文字列が以下の条件を満たすようにしたいです。
- 長さが偶数であり、奇数文字目が
iで偶数文字目がoである。
挿入する必要のある文字数の最小値を求めて下さい。なお、問題の制約下で、有限個の文字を適切に挿入することで、S が条件をみたすようにできることが証明できます。
制約
- S は
i,oからなる長さ 1 以上 100 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
ioi
出力例 1
1
3 文字目のあとに o を挿入して ioio とすることで、条件を満たすことができます。0 文字以下の挿入で条件を満たすことはできません。
入力例 2
iioo
出力例 2
2
1 文字目のあとに o を、3 文字目のあとに i を挿入することで、条件を満たすことができます。1 文字以下の挿入で条件を満たすことはできません。
入力例 3
io
出力例 3
0
S がすでに条件を満たします。
Score : 250 points
Problem Statement
Takahashi aggregated usage records from ticket gates. However, he accidentally erased some records of entering and exiting stations. He is trying to restore the erased records.
You are given a string S consisting of i and o. We want to insert zero or more characters at arbitrary positions in S so that the resulting string satisfies the following conditions:
- Its length is even, and every odd-numbered (1st, 3rd, ...) character is
iwhile every even-numbered (2nd, 4th, ...) character iso.
Find the minimum number of characters that need to be inserted. It can be proved under the constraints of this problem that by inserting an appropriate finite number of characters, S can be made to satisfy the conditions.
Constraints
- S is a string of length between 1 and 100, consisting of
iando.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
ioi
Sample Output 1
1
We can insert o after the 3rd character to form ioio to satisfy the conditions. The conditions cannot be satisfied by inserting zero or fewer characters.
Sample Input 2
iioo
Sample Output 2
2
We can insert o after the 1st character and i after the 3rd character to satisfy the conditions. The conditions cannot be satisfied by inserting one or fewer characters.
Sample Input 3
io
Sample Output 3
0
S already satisfies the conditions.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 350 点
問題文
N 頂点 M 辺の単純な無向グラフがあります。 グラフは頂点 1, 頂点 2,\ldots, 頂点 N からなり、i 番目 (1\le i\le M) の辺は頂点 u _ i と頂点 v _ i を結んでいます。
あなたは、次の操作を 0 回以上行います。
- まだ削除されていない辺をひとつ選び、削除する。
あなたの目的はグラフを二部グラフにすることです。 操作を行ったあとのグラフを二部グラフにするために、最低でも何回操作を行う必要があるか求めてください。
グラフが単純であるとは
グラフが単純であるとは、自己ループ(u _ i=v _ i となる辺)や多重辺(u _ i=u _ j かつ v _ i=v _ j となる辺のペア)が存在しないことをいいます。
二部グラフとは
二部グラフとは、頂点をそれぞれ黒か白のどちらか一色で塗り、次の条件を満たすことができるグラフのことをいいます。
- どの辺についても、その辺が結んでいるふたつの頂点に塗られた色は異なる。
制約
- 2\le N\le10
- 1\le M\le\dfrac{N(N-1)}2
- 1\le u _ i\lt v _ i\le N\ (1\le i\le M)
- 与えられるグラフは単純
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M u _ 1 v _ 1 u _ 2 v _ 2 \vdots u _ M v _ M
出力
操作を行ったあとのグラフを二部グラフにするために、行う必要がある操作の回数を出力せよ。
入力例 1
5 8 1 2 1 3 1 4 2 3 2 5 3 4 3 5 4 5
出力例 1
2
例えば、頂点 1 と頂点 3 を結ぶ辺、頂点 3 と頂点 5 を結ぶ辺の 2 つを削除することでグラフを二部グラフにすることができます。
操作を 1 回以下行うことでグラフを二部グラフにすることはできないため、2 を出力してください。
入力例 2
2 1 1 2
出力例 2
0
グラフははじめから二部グラフです。 よって、行う必要がある操作の回数は 0 回です。
入力例 3
10 20 5 9 1 4 3 8 1 6 4 10 5 7 5 6 3 7 3 6 5 10 1 3 3 4 6 7 1 2 4 7 1 5 1 9 9 10 4 5 8 9
出力例 3
5
Score : 350 points
Problem Statement
There is a simple undirected graph with N vertices and M edges. The graph consists of vertex 1, vertex 2,\ldots, vertex N, and the i-th edge (1\le i\le M) connects vertices u _ i and v _ i.
You will perform the following operation zero or more times:
- Choose one edge that has not been deleted yet, and delete it.
Your goal is to make the graph bipartite. Find the minimum number of operations needed to make the graph after the operations bipartite.
What it means for a graph to be simple?
A graph is simple if and only if it has no self-loops (edges where u _ i=v _ i) or multi-edges (pairs of edges where u _ i=u _ j and v _ i=v _ j).
What is a bipartite graph?
A bipartite graph is a graph where it is possible to color each vertex black or white satisfying the following condition:
- For every edge, the two vertices connected by that edge have different colors.
Constraints
- 2\le N\le10
- 1\le M\le\dfrac{N(N-1)}2
- 1\le u _ i\lt v _ i\le N\ (1\le i\le M)
- The given graph is simple.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M u _ 1 v _ 1 u _ 2 v _ 2 \vdots u _ M v _ M
Output
Print the number of operations that need to be performed to make the graph bipartite.
Sample Input 1
5 8 1 2 1 3 1 4 2 3 2 5 3 4 3 5 4 5
Sample Output 1
2
You can make the graph bipartite by deleting two edges: for example, the edge connecting vertices 1 and 3, and the edge connecting vertices 3 and 5.
It is impossible to make the graph bipartite by performing one or less operations, so print 2.
Sample Input 2
2 1 1 2
Sample Output 2
0
The graph is bipartite from the beginning. Thus, the number of operations that need to be performed is 0.
Sample Input 3
10 20 5 9 1 4 3 8 1 6 4 10 5 7 5 6 3 7 3 6 5 10 1 3 3 4 6 7 1 2 4 7 1 5 1 9 9 10 4 5 8 9
Sample Output 3
5
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
英小文字、,、" からなる長さ N の文字列 S が与えられます。S に含まれる " の個数は偶数であることが保証されています。
S に含まれる " の個数を 2K 個とすると、各 i=1,2,\ldots,K について 2i-1 番目の " から 2i 番目の " までの文字のことを 括られた文字 と呼びます。
あなたの仕事は、 S に含まれる , のうち、括られた文字 でないもの を . で置き換えて得られる文字列を答えることです。
制約
- N は 1 以上 2\times 10^5 以下の整数
- S は英小文字、
,、"からなる長さ N の文字列 - S に含まれる
"の個数は偶数
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
答えを出力せよ。
入力例 1
8 "a,b"c,d
出力例 1
"a,b"c.d
S のうち "a,b" が括られた文字であり、c,d は括られた文字ではありません。
S に含まれる , のうち、括られた文字でないのは S の左から 7 番目の文字なので、7 番目の文字を . で置き換えたものが答えとなります。
入力例 2
5 ,,,,,
出力例 2
.....
入力例 3
20 a,"t,"c,"o,"d,"e,"r,
出力例 3
a."t,"c."o,"d."e,"r.
Score : 300 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters, ,, and ". It is guaranteed that S contains an even number of ".
Let 2K be the number of " in S. For each i=1,2,\ldots,K, the characters from the (2i-1)-th " through the (2i)-th " are said to be enclosed.
Your task is to replace each , in S that is not an enclosed character with . and print the resulting string.
Constraints
- N is an integer between 1 and 2\times 10^5, inclusive.
- S is a string of length N consisting of lowercase English letters,
,, and". - S contains an even number of
".
Input
The input is given from Standard Input in the following format:
N S
Output
Print the answer.
Sample Input 1
8 "a,b"c,d
Sample Output 1
"a,b"c.d
In S, "a,b" are enclosed characters, and c,d are not.
The , in S that is not an enclosed character is the seventh character from the left in S, so replace that character with . to get the answer.
Sample Input 2
5 ,,,,,
Sample Output 2
.....
Sample Input 3
20 a,"t,"c,"o,"d,"e,"r,
Sample Output 3
a."t,"c."o,"d."e,"r.
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君は N 種類の硬貨をそれぞれ何枚か持っており、 具体的には、1\leq i\leq N について A_i 円硬貨を B_i 枚持っています。
高橋君が現在持っている硬貨を用いて、(お釣りが出ないように)ちょうど X 円を支払うことができるか判定してください。
制約
- 1\leq N\leq 50
- 1\leq X\leq 10^4
- 1\leq A_i\leq 100
- 1\leq B_i\leq 50
- A_i はすべて異なる。
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
高橋君が現在持っている硬貨を用いてちょうど X 円を支払うことができる場合は Yes を、
できない場合は No を出力せよ。
入力例 1
2 19 2 3 5 6
出力例 1
Yes
高橋君は 2 円硬貨を 3 枚、5 円硬貨を 6 枚持っています。
このうち、2 円硬貨を 2 枚、5 円硬貨を 3 枚用いることでちょうど 2\times 2+5\times 3=19 円を支払うことができます。
よって、Yes を出力します。
入力例 2
2 18 2 3 5 6
出力例 2
No
持っている硬貨をどのように組み合わせてもちょうど 18 円を支払うことはできません。
よって、No を出力します。
入力例 3
3 1001 1 1 2 1 100 10
出力例 3
Yes
1 枚も使用しない硬貨が存在しても構いません。
Score : 400 points
Problem Statement
Takahashi has N kinds of coins; specifically, for 1\leq i\leq N, he has B_i coins worth A_i yen (the currency in Japan) each.
Determine if Takahashi can pay exactly X yen (without change) with the coins he currently has.
Constraints
- 1\leq N\leq 50
- 1\leq X\leq 10^4
- 1\leq A_i\leq 100
- 1\leq B_i\leq 50
- A_i are pairwise distinct.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N X A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print Yes if Takahashi can pay exactly X yen with the coins he currently has;
print No otherwise.
Sample Input 1
2 19 2 3 5 6
Sample Output 1
Yes
Takahashi has three 2-yen coins and six 5-yen coins.
He can use two 2-yen coins and three 5-yen coins to pay exactly 2\times 2+5\times 3=19 yen.
Thus, Yes should be printed.
Sample Input 2
2 18 2 3 5 6
Sample Output 2
No
There is no combination of the coins that he can use to pay exactly 18 yen.
Thus, No should be printed.
Sample Input 3
3 1001 1 1 2 1 100 10
Sample Output 3
Yes
He need not use all kinds of coins.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 450 点
問題文
A, B, C の 3 種類の文字からなる長さ N の文字列 S が与えられます。
S の空でない連続する部分文字列は \dfrac{N(N+1)}2 個ありますが、そのうち A が B よりも多く含まれるものはいくつあるか求めてください。
2 つの部分文字列は、S から取り出す場所が異なれば文字列として等しくても区別して数えることに注意してください。
部分文字列とは
S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。
例えば、AB は ABC の部分文字列ですが、AC は ABC の部分文字列ではありません。
制約
- 1\le N\le5\times10 ^ 5
- S は
A,B,Cからなる長さ N の文字列 - N は整数
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
S の連続する部分文字列のうち A が B よりも多く含まれるものの個数を出力せよ。
入力例 1
10 ACBBCABCAB
出力例 1
8
以下の 8 つの部分文字列が条件を満たします。
A:S の 1 文字目から 1 文字目AC:S の 1 文字目から 2 文字目CA:S の 5 文字目から 6 文字目CABCA:S の 5 文字目から 9 文字目A:S の 6 文字目から 6 文字目ABCA:S の 6 文字目から 9 文字目CA:S の 8 文字目から 9 文字目A:S の 9 文字目から 9 文字目
これら以外の部分文字列は条件を満たさないため、8 を出力してください。
A や CA は複数箇所から取り出すことができますが、取り出す場所が異なれば区別して数えることに注意してください。
入力例 2
4 CCBC
出力例 2
0
条件を満たす部分文字列が存在しないこともあります。
入力例 3
36 CABACBBBBBAABABACCBCABCCABAABABBCBAC
出力例 3
136
Score : 450 points
Problem Statement
You are given a string S of length N consisting of three kinds of characters: A, B, and C.
There are \dfrac{N(N+1)}2 non-empty contiguous substrings of S. Find how many of them contain more As than Bs.
Note that two substrings are counted separately if they are taken from different positions in S, even if they are equal as strings.
What is a substring?
A substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, AB is a substring of ABC, but AC is not a substring of ABC.
Constraints
- 1\le N\le5\times10 ^ 5
- S is a string of length N consisting of
A,B, andC. - N is an integer.
Input
The input is given from Standard Input in the following format:
N S
Output
Print the number of contiguous substrings of S that contain more As than Bs.
Sample Input 1
10 ACBBCABCAB
Sample Output 1
8
The following eight substrings satisfy the condition:
A: 1st to 1st character of SAC: 1st to 2nd character of SCA: 5th to 6th character of SCABCA: 5th to 9th character of SA: 6th to 6th character of SABCA: 6th to 9th character of SCA: 8th to 9th character of SA: 9th to 9th character of S
All other substrings do not satisfy the condition, so print 8.
Note that A and CA can be taken from multiple positions, but they are counted separately if taken from different positions.
Sample Input 2
4 CCBC
Sample Output 2
0
There may be no substrings that satisfy the condition.
Sample Input 3
36 CABACBBBBBAABABACCBCABCCABAABABBCBAC
Sample Output 3
136
実行時間制限: 4 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
1, 2, \ldots, N の番号がついた N 個の箱があり、はじめ箱 i には色 C_i のボールが 1 つ入っています。
Q 個のクエリが与えられるので、これらを順に処理してください。
各クエリは整数の組 (a,b) によって与えられ、その内容は以下の通りです。
- 箱 a のボールをすべて箱 b に移し、その後箱 b に何種類の色のボールが入っているかを出力する。
ただし、箱 a や箱 b が空の場合もあることに注意してください。
制約
- 1 \leq N, Q \leq 200000
- 1 \leq C_i \leq N
- 1 \leq a, b \leq N
- a \neq b
- 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。ここで、 \text{query}_i は i 番目のクエリを意味する。
N Q
C_1 C_2 \ldots C_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
各クエリは次の形式で与えられる。
a b
出力
Q 行出力せよ。 i 行目には i 番目のクエリに対する答えを出力せよ。
入力例 1
6 5 1 1 1 2 2 3 1 2 6 4 5 1 3 6 4 6
出力例 1
1 2 1 1 3
-
1 番目のクエリでは、箱 1 のボールをすべて箱 2 に移します。箱 2 には色 1 のボールが 2 つ入っている状態となるため、1 を出力します。
-
2 番目のクエリでは、箱 6 のボールをすべて箱 4 に移します。箱 4 には色 2 のボールが 1 つ、色 3 のボールが 1 つ入っている状態となるため、2 を出力します。
-
3 番目のクエリでは、箱 5 のボールをすべて箱 1 に移します。箱 1 には色 2 のボールが 1 つ入っている状態となるため、1 を出力します。
-
4 番目のクエリでは、箱 3 のボールをすべて箱 6 に移します。箱 6 には色 1 のボールが 1 つ入っている状態となるため、1 を出力します。
-
5 番目のクエリでは、箱 4 のボールをすべて箱 6 に移します。箱 6 には色 1 のボールが 1 つ、色 2 のボールが 1 つ、色 3 のボールが 1 つ入っている状態となるため、3 を出力します。
入力例 2
5 3 2 4 2 4 2 3 1 2 5 3 2
出力例 2
1 2 0
Score : 500 points
Problem Statement
There are N boxes numbered 1, 2, \ldots, N. Initially, box i contains one ball of color C_i.
You are given Q queries, which you should process in order.
Each query is given by a pair of integers (a,b) and asks you to do the following:
- Move all the balls from box a to box b, and then print the number of different colors of balls in box b.
Here, the boxes a and b may be empty.
Constraints
- 1 \leq N, Q \leq 200000
- 1 \leq C_i \leq N
- 1 \leq a, b \leq N
- a \neq b
- All input values are integers.
Input
The input is given from Standard Input in the following format, where \text{query}_i represents the i-th query:
N Q
C_1 C_2 \ldots C_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
Each query is given in the following format:
a b
Output
Print Q lines. The i-th line should contain the response to the i-th query.
Sample Input 1
6 5 1 1 1 2 2 3 1 2 6 4 5 1 3 6 4 6
Sample Output 1
1 2 1 1 3
-
For the first query, move all the balls from box 1 to box 2. Box 2 now contains two balls of color 1, so print 1.
-
For the second query, move all the balls from box 6 to box 4. Box 4 now contains one ball of color 2 and one ball of color 3, so print 2.
-
For the third query, move all the balls from box 5 to box 1. Box 1 now contains one ball of color 2, so print 1.
-
For the fourth query, move all the balls from box 3 to box 6. Box 6 now contains one ball of color 1, so print 1.
-
For the fifth query, move all the balls from box 4 to box 6. Box 6 now contains one ball of color 1, one ball of color 2, and one ball of color 3, so print 3.
Sample Input 2
5 3 2 4 2 4 2 3 1 2 5 3 2
Sample Output 2
1 2 0