A - New Scheme

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

8 個の整数 S_1,S_2,\dots,S_8 が与えられます。 以下の 3 つの条件が全て満たされるならば Yes を、そうでないならば No を出力してください。

  • 数列 (S_1,S_2,\dots,S_8) は広義単調増加である。すなわち、S_1 \leq S_2 \leq \dots \leq S_8 である。
  • S_1,S_2,\dots,S_8 は全て 100 以上 675 以下である。
  • S_1,S_2,\dots,S_8 は全て 25 の倍数である。

制約

  • 0\leq S_i \leq 1000
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

S_1 S_2 \dots S_8

出力

答えを出力せよ。


入力例 1

125 175 250 300 400 525 600 650

出力例 1

Yes

3 つの条件を全て満たしています。


入力例 2

100 250 300 400 325 575 625 675

出力例 2

No

S_4 > S_5 であるため、1 つ目の条件を満たしていません。


入力例 3

0 23 24 145 301 413 631 632

出力例 3

No

2 つ目の条件と 3 つ目の条件を満たしていません。

Score : 100 points

Problem Statement

Given eight integers S_1,S_2,\dots, and S_8, print Yes if they satisfy all of the following three conditions, and No otherwise.

  • The sequence (S_1,S_2,\dots,S_8) is monotonically non-decreasing. In other words, S_1 \leq S_2 \leq \dots \leq S_8.
  • S_1,S_2,\dots, and S_8 are all between 100 and 675, inclusive.
  • S_1,S_2,\dots, and S_8 are all multiples of 25.

Constraints

  • 0\leq S_i \leq 1000
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

S_1 S_2 \dots S_8

Output

Print the answer.


Sample Input 1

125 175 250 300 400 525 600 650

Sample Output 1

Yes

They satisfy all of the three conditions.


Sample Input 2

100 250 300 400 325 575 625 675

Sample Output 2

No

They violate the first condition because S_4 > S_5.


Sample Input 3

0 23 24 145 301 413 631 632

Sample Output 3

No

They violate the second and third conditions.

B - Rightmost

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

英小文字からなる文字列 S が与えられます。
S に a が現れるならば最後に現れるのが何文字目かを出力し、現れないならば -1 を出力してください。

制約

  • S は英小文字からなる長さ 1 以上 100 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

S

出力

答えを出力せよ。


入力例 1

abcdaxayz

出力例 1

7

S に a は 3 回現れますが、最後に現れるのは 7 文字目なので、7 を出力します。


入力例 2

bcbbbz

出力例 2

-1

S に a は現れないので、-1 を出力します。


入力例 3

aaaaa

出力例 3

5

Score : 100 points

Problem Statement

You are given a string S consisting of lowercase English letters.
If a appears in S, print the last index at which it appears; otherwise, print -1. (The index starts at 1.)

Constraints

  • S is a string of length between 1 and 100 (inclusive) consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

S

Output

Print the answer.


Sample Input 1

abcdaxayz

Sample Output 1

7

a appears three times in S. The last occurrence is at index 7, so you should print 7.


Sample Input 2

bcbbbz

Sample Output 2

-1

a does not appear in S, so you should print -1.


Sample Input 3

aaaaa

Sample Output 3

5
C - Counterclockwise Rotation

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

x 軸の正の向きが右、y 軸の正の向きが上であるような xy 座標平面において、点 (a,b) を原点を中心として反時計回りに d 度回転させた点を求めてください。

制約

  • -1000 \leq a,b \leq 1000
  • 1 \leq d \leq 360
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

a b d

出力

求めるべき点を (a',b') とするとき、 a' と b' をこの順に空白区切りで出力せよ。
なお、各出力について、解との絶対誤差または相対誤差が 10^{−6} 以下であれば正解として扱われる。


入力例 1

2 2 180

出力例 1

-2 -2

(2,2) を原点を中心として反時計回りに 180 度回転させた点は、(2,2) を原点について対称な位置に移動させた点であり、(-2,-2) となります。


入力例 2

5 0 120

出力例 2

-2.49999999999999911182 4.33012701892219364908

(5,0) を原点を中心として反時計回りに 120 度回転させた点は (-\frac {5}{2} , \frac {5\sqrt{3}}{2}) です。
この例での出力はこれらの値と厳密には一致しませんが、誤差が十分に小さいため正解として扱われます。


入力例 3

0 0 11

出力例 3

0.00000000000000000000 0.00000000000000000000

(a,b) が原点(回転の中心)なので回転させても座標が変わりません。


入力例 4

15 5 360

出力例 4

15.00000000000000177636 4.99999999999999555911

360 度回転させたので座標が変わりません。


入力例 5

-505 191 278

出力例 5

118.85878514480690171240 526.66743699786547949770

Score : 200 points

Problem Statement

In an xy-coordinate plane whose x-axis is oriented to the right and whose y-axis is oriented upwards, rotate a point (a, b) around the origin d degrees counterclockwise and find the new coordinates of the point.

Constraints

  • -1000 \leq a,b \leq 1000
  • 1 \leq d \leq 360
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

a b d

Output

Let the new coordinates of the point be (a', b'). Print a' and b' in this order, with a space in between.
Your output will be considered correct when, for each value printed, the absolute or relative error from the answer is at most 10^{-6}.


Sample Input 1

2 2 180

Sample Output 1

-2 -2

When (2, 2) is rotated around the origin 180 degrees counterclockwise, it becomes the symmetric point of (2, 2) with respect to the origin, which is (-2, -2).


Sample Input 2

5 0 120

Sample Output 2

-2.49999999999999911182 4.33012701892219364908

When (5, 0) is rotated around the origin 120 degrees counterclockwise, it becomes (-\frac {5}{2} , \frac {5\sqrt{3}}{2}).
This sample output does not precisely match these values, but the errors are small enough to be considered correct.


Sample Input 3

0 0 11

Sample Output 3

0.00000000000000000000 0.00000000000000000000

Since (a, b) is the origin (the center of rotation), a rotation does not change its coordinates.


Sample Input 4

15 5 360

Sample Output 4

15.00000000000000177636 4.99999999999999555911

A 360-degree rotation does not change the coordinates of a point.


Sample Input 5

-505 191 278

Sample Output 5

118.85878514480690171240 526.66743699786547949770
D - Nice Grid

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

次の図に示す、各マスが黒または白に塗られた縦 15 行 \times 横 15 列のグリッドにおいて、 上から R 行目、左から C 列目のマスが何色かを出力して下さい。

制約

  • 1 \leq R, C \leq 15
  • R, C は整数

入力

入力は以下の形式で標準入力から与えられる。

R C

出力

図のグリッドにおいて上から R 行目、左から C 列目のマスが黒色の場合は black と、白色の場合は white と出力せよ。 ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。


入力例 1

3 5

出力例 1

black

図のグリッドにおいて上から 3 行目、左から 5 列目のマスは黒色です。 よって、black と出力します。


入力例 2

4 5

出力例 2

white

図のグリッドにおいて上から 4 行目、左から 5 列目のマスは白色です。 よって、white と出力します。

Score : 200 points

Problem Statement

Print the color of the cell at the R-th row from the top and C-th column from the left in the following grid with 15 vertical rows and 15 horizontal columns.

Constraints

  • 1 \leq R, C \leq 15
  • R and C are integers.

Input

Input is given from Standard Input in the following format:

R C

Output

In the grid above, if the color of the cell at the R-th row from the top and C-th column from the left is black, then print black; if the cell is white, then print white. Note that the judge is case-sensitive.


Sample Input 1

3 5

Sample Output 1

black

In the grid above, the cell at the 3-rd row from the top and 5-th column from the left is black. Thus, black should be printed.


Sample Input 2

4 5

Sample Output 2

white

In the grid above, the cell at the 4-th row from the top and 5-th column from the left is white. Thus, white should be printed.

E - Paint to make a rectangle

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

H 行 W 列のマス目が与えられます。
以下、上から i 行目 (1\leq i\leq H) かつ左から j 列目 (1\leq j\leq W) のマスをマス (i,j) で表します。
マス目の状態は H 個の長さ W の文字列 S_1,S_2, \ldots, S_H によって以下のように表されます。

  • S_i の j 文字目が # のとき、マス (i,j) は黒く塗られている。
  • S_i の j 文字目が . のとき、マス (i,j) は白く塗られている。
  • S_i の j 文字目が ? のとき、マス (i,j) は塗られていない。

高橋君はまだ塗られていないマスをそれぞれ白または黒で塗ることで、黒マス全体が長方形をなすようにしたいです。
より具体的には、ある 4 つの整数の組 (a,b,c,d) (1\leq a\leq b\leq H, 1\leq c\leq d\leq W) が存在して、次が成り立つようにしたいです。

マス (i,j) (1\leq i\leq H, 1\leq j\leq W) は、 a\leq i\leq b かつ c\leq j\leq d をみたすとき、黒く塗られている。
そうでないとき、白く塗られている。

そのようなことが可能か判定してください。

制約

  • 1\leq H,W\leq 1000
  • H, W は整数
  • S_i は #, ., ? のみからなる長さ W の文字列
  • 黒く塗られたマスが 1 つ以上存在する。

入力

入力は以下の形式で標準入力から与えられる。

H W
S_1
S_2
\vdots
S_H

出力

まだ塗られていないマスをそれぞれ白または黒で塗ることで、黒マス全体が長方形をなすようにできるならば Yes を、そうでないならば No を出力せよ。


入力例 1

3 5
.#?#.
.?#?.
?...?

出力例 1

Yes

マス目は以下の状態になっています。? のマスがまだ塗られていないマスです。

マス (1,3), (2,2), (2,4) を黒く塗り、マス (3,1), (3,5) を白く塗ることで、 以下のように黒マス全体が長方形をなすようにできます。

よって、Yes を出力します。


入力例 2

3 3
?##
#.#
##?

出力例 2

No

黒マス全体が長方形をなすためには、少なくともマス (2,2) を黒く塗る必要がありますがすでに白く塗られています。
よって、黒マス全体が長方形をなすようにマス目を塗ることはできないため、No を出力します。


入力例 3

1 1
#

出力例 3

Yes

Score : 300 points

Problem Statement

You are given a grid of H rows and W columns.
Let (i,j) denote the cell at row i (1 \leq i \leq H) from the top and column j (1 \leq j \leq W) from the left.
The state of the grid is represented by H strings S_1, S_2, \ldots, S_H, each of length W, as follows:

  • If the j-th character of S_i is #, cell (i,j) is painted black.
  • If the j-th character of S_i is ., cell (i,j) is painted white.
  • If the j-th character of S_i is ?, cell (i,j) is not yet painted.

Takahashi wants to paint each not-yet-painted cell white or black so that all the black cells form a rectangle.
More precisely, he wants there to exist a quadruple of integers (a,b,c,d) (1 \leq a \leq b \leq H, 1 \leq c \leq d \leq W) such that:

For each cell (i,j) (1 \leq i \leq H, 1 \leq j \leq W), if a \leq i \leq b and c \leq j \leq d, the cell is black;
otherwise, the cell is white.

Determine whether this is possible.

Constraints

  • 1 \leq H, W \leq 1000
  • H and W are integers.
  • Each S_i is a string of length W consisting of #, ., ?.
  • There is at least one cell that is already painted black.

Input

The input is given from Standard Input in the following format:

H W
S_1
S_2
\vdots
S_H

Output

If it is possible to paint all the not-yet-painted cells so that the black cells form a rectangle, print Yes; otherwise, print No.


Sample Input 1

3 5
.#?#.
.?#?.
?...?

Sample Output 1

Yes

The grid is in the following state. ? indicates a cell that are not yet painted.

By painting cells (1,3), (2,2), and (2,4) black and cells (3,1) and (3,5) white, the black cells can form a rectangle as follows:

Therefore, print Yes.


Sample Input 2

3 3
?##
#.#
##?

Sample Output 2

No

To form a rectangle with all black cells, you would need to paint cell (2,2) black, but it is already painted white.
Therefore, it is impossible to make all black cells form a rectangle, so print No.


Sample Input 3

1 1
#

Sample Output 3

Yes
F - Don’t be cycle

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1 から N の番号がついており、i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。 このグラフから 0 本以上のいくつかの辺を削除してグラフが閉路を持たないようにするとき、削除する辺の本数の最小値を求めてください。

単純無向グラフとは 単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。

閉路とは 単純無向グラフが閉路を持つとは、i \neq j ならば v_i \neq v_j を満たす長さ 3 以上の頂点列 (v_0, v_1, \ldots, v_{n-1}) であって、各 0 \leq i < n に対し v_i と v_{i+1 \bmod n} の間に辺が存在するものがあることをいいます。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • 与えられるグラフは単純
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

答えを出力せよ。


入力例 1

6 7
1 2
1 3
2 3
4 2
6 5
4 6
4 5

出力例 1

2

頂点 1 と頂点 2 を結ぶ辺・頂点 4 と頂点 5 を結ぶ辺の 2 本を削除するなどの方法でグラフが閉路を持たないようにすることができます。
1 本以下の辺の削除でグラフが閉路を持たないようにすることはできないので、2 を出力します。


入力例 2

4 2
1 2
3 4

出力例 2

0

入力例 3

5 3
1 2
1 3
2 3

出力例 3

1

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Let us delete zero or more edges to remove cycles from the graph. Find the minimum number of edges that must be deleted for this purpose.

What is a simple undirected graph? A simple undirected graph is a graph without self-loops or multi-edges whose edges have no direction.

What is a cycle? A cycle in a simple undirected graph is a sequence of vertices (v_0, v_1, \ldots, v_{n-1}) of length at least 3 satisfying v_i \neq v_j if i \neq j such that for each 0 \leq i < n, there is an edge between v_i and v_{i+1 \bmod n}.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • The given graph is simple.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

Print the answer.


Sample Input 1

6 7
1 2
1 3
2 3
4 2
6 5
4 6
4 5

Sample Output 1

2

One way to remove cycles from the graph is to delete the two edges between vertex 1 and vertex 2 and between vertex 4 and vertex 5.
There is no way to remove cycles from the graph by deleting one or fewer edges, so you should print 2.


Sample Input 2

4 2
1 2
3 4

Sample Output 2

0

Sample Input 3

5 3
1 2
1 3
2 3

Sample Output 3

1
G - Diagonal Separation

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 425 点

問題文

N 行 N 列のグリッドがあります。高橋君は以下の条件を満たすように各マスを黒または白のいずれかに塗り分けたいと考えています。

  • すべての行について以下の条件が成り立つ。
    • ある整数 i\ (0\leq i\leq N) が存在して、その行の左から i 個のマスは黒、それ以外は白で塗られている。
  • すべての列について以下の条件が成り立つ。
    • ある整数 i\ (0\leq i\leq N) が存在して、その列の上から i 個のマスは黒、それ以外は白で塗られている。

M 個のマスがすでに塗られています。そのうち i 個目は上から X_i 行目、左から Y_i 列目のマスで、C_i が B のとき黒で、 W のとき白で塗られています。

高橋君はまだ塗られていない残りの N^2-M 個のマスの色をうまく決めることで条件を満たすことができるか判定してください。

制約

  • 1\leq N\leq 10^9
  • 1\leq M\leq \min(N^2,2\times 10^5)
  • 1\leq X_i,Y_i\leq N
  • (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
  • C_i は B または W
  • 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
X_1 Y_1 C_1
\vdots
X_M Y_M C_M

出力

条件を満たすことができるとき Yes を、そうでないとき No を出力せよ。


入力例 1

4 3
4 1 B
3 2 W
1 3 B

出力例 1

Yes

例えば以下の図のように色を塗り分けると条件を満たすことができます。すでに塗られているマスを赤色の線で囲んでいます。


入力例 2

2 2
1 2 W
2 2 B

出力例 2

No

塗られていない残りの 2 つのマスをどのように塗っても,条件を満たすことはできません。


入力例 3

1 1
1 1 W

出力例 3

Yes

入力例 4

2289 10
1700 1083 W
528 967 B
1789 211 W
518 1708 W
1036 779 B
136 657 B
759 1497 B
902 1309 B
1814 712 B
936 763 B

出力例 4

No

Score : 425 points

Problem Statement

There is an N \times N grid. Takahashi wants to color each cell black or white so that all of the following conditions are satisfied:

  • For every row, the following condition holds:
    • There exists an integer i\ (0\leq i\leq N) such that the leftmost i cells are colored black, and the rest are colored white.
  • For every column, the following condition holds:
    • There exists an integer i\ (0\leq i\leq N) such that the topmost i cells are colored black, and the rest are colored white.

Out of these N^2 cells, M of them have already been colored. Among them, the i-th one is at the X_i-th row from the top and the Y_i-th column from the left, and it is colored black if C_i is B and white if C_i is W.

Determine whether he can color the remaining uncolored N^2 - M cells so that all the conditions are satisfied.

Constraints

  • 1\leq N\leq 10^9
  • 1\leq M\leq \min(N^2,2\times 10^5)
  • 1\leq X_i,Y_i\leq N
  • (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
  • C_i is B or W.
  • All input numbers are integers.

Input

The input is given from Standard Input in the following format:

N M
X_1 Y_1 C_1
\vdots
X_M Y_M C_M

Output

If it is possible to satisfy the conditions, print Yes; otherwise, print No.


Sample Input 1

4 3
4 1 B
3 2 W
1 3 B

Sample Output 1

Yes

For example, one can color the grid as in the following figure to satisfy the conditions. The cells already colored are surrounded by red borders.


Sample Input 2

2 2
1 2 W
2 2 B

Sample Output 2

No

No matter how the remaining two cells are colored, the conditions cannot be satisfied.


Sample Input 3

1 1
1 1 W

Sample Output 3

Yes

Sample Input 4

2289 10
1700 1083 W
528 967 B
1789 211 W
518 1708 W
1036 779 B
136 657 B
759 1497 B
902 1309 B
1814 712 B
936 763 B

Sample Output 4

No
H - Work or Rest

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

高橋君が住む世界の一週間は N 日からなります。
一週間は曜日 1,2,\dots,N と進んでいき、曜日 N が終わると次の週の曜日 1 が始まります。

ABC 国の国王である高橋君は、各曜日に「平日」「休日」のどちらかを割り当てます。この割り当ては毎週同じでなければなりません。また、少なくとも 1 つの曜日を「休日」に割り当てなければなりません。

この条件の下で、曜日 i の生産量は長さ N の数列 A を用いて以下のように定義されます。

  • 曜日 i が「休日」である場合は 0
  • 曜日 i が「平日」のとき、直前の休日が x 日前、直後の休日が y 日後である場合は A_{\min(x,y)}
    • 割り当ては毎週繰り返されるため、 直前 / 直後 の「休日」が当日とは別の週に属する可能性があることに注意してください。詳しくはサンプルを参照してください。

上手く割り当てを決めたときの一週間当たりの生産量の最大値を答えてください。
但し、一週間当たりの生産量とは曜日 1,2,\dots,N の生産量の総和を指します。

制約

  • 入力はすべて整数
  • 1 \le N \le 5000
  • 1 \le A_i \le 10^9

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

答えを整数として出力せよ。


入力例 1

7
10 10 1 1 1 1 1

出力例 1

50

例えば曜日 2,4 を「休日」、残りを「平日」に割り当てることで、以下のように一週間当たりの生産量 50 を達成できます。

  • 曜日 1 ... x=4,y=1 なので、この曜日の生産量は A_1 = 10 である。
  • 曜日 2 ... 「休日」であるので、この曜日の生産量は 0 である。
  • 曜日 3 ... x=1,y=1 なので、この曜日の生産量は A_1 = 10 である。
  • 曜日 4 ... 「休日」であるので、この曜日の生産量は 0 である。
  • 曜日 5 ... x=1,y=4 なので、この曜日の生産量は A_1 = 10 である。
  • 曜日 6 ... x=2,y=3 なので、この曜日の生産量は A_2 = 10 である。
  • 曜日 7 ... x=3,y=2 なので、この曜日の生産量は A_2 = 10 である。

一週間当たりの生産量を 51 以上にすることはできません。


入力例 2

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

出力例 2

5100000000

入力例 3

20
38 7719 21238 2437 8855 11797 8365 32285 10450 30612 5853 28100 1142 281 20537 15921 8945 26285 2997 14680

出力例 3

236980

Score : 500 points

Problem Statement

In the world where Takahashi lives, a week has N days.

Takahashi, the king of the Kingdom of AtCoder, assigns "weekday" or "holiday" to each day of week. The assignments should be the same for all weeks. At least one day of week should be assigned "holiday".

Under such conditions, the productivity of the i-th day of week is defined by a sequence A of length N as follows:

  • if the i-th day of week is "holiday", its productivity is 0;
  • if the i-th day of week is "weekday", its productivity is A_{\min(x,y)}, if the last holiday is x days before and the next one is y days after.
    • Note that the last/next holiday may belong to a different week due to the periodic assignments. For details, see the Samples.

Find the maximum productivity per week when the assignments are chosen optimally.
Here, the productivity per week refers to the sum of the productivities of the 1-st, 2-nd, \dots, and N-th day of week.

Constraints

  • All values in the input are integers.
  • 1 \le N \le 5000
  • 1 \le A_i \le 10^9

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answer as an integer.


Sample Input 1

7
10 10 1 1 1 1 1

Sample Output 1

50

For example, we can assign "holiday" to the 2-nd and 4-th day of week and "weekday" to the rest to achieve a productivity of 50 per week:

  • the 1-st day of week ... x=4 and y=1, so its productivity is A_1 = 10.
  • the 2-nd day of week ... it is holiday, so its productivity is 0.
  • the 3-st day of week ... x=1 and y=1, so its productivity is A_1 = 10.
  • the 4-th day of week ... it is holiday, so its productivity is 0.
  • the 5-th day of week ... x=1 and y=4, so its productivity is A_1 = 10.
  • the 6-th day of week ... x=2 and y=3, so its productivity is A_2 = 10.
  • the 7-th day of week ... x=3 and y=2, so its productivity is A_2 = 10.

It is impossible to make the productivity per week 51 or greater.


Sample Input 2

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

Sample Output 2

5100000000

Sample Input 3

20
38 7719 21238 2437 8855 11797 8365 32285 10450 30612 5853 28100 1142 281 20537 15921 8945 26285 2997 14680

Sample Output 3

236980
I - Connecting Points

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

2 次元平面上に N 頂点 0 辺のグラフ G があります。頂点には 1 から N までの番号が付いており、頂点 i は座標 (x_i,y_i) にあります。

G の頂点 u,v に対して、u,v の距離 d(u,v) をマンハッタン距離 d(u,v)=|x_u-x_v|+|y_u-y_v| で定義します。

また、G の 2 つの連結成分 A,B に対して、A,B の頂点集合をそれぞれ V(A),V(B) としたとき、A,B の距離 d(A,B) を d(A,B)=\min\lbrace d(u,v)\mid u \in V(A), v\in V(B)\rbrace で定義します。

以下で説明されるクエリを Q 個処理してください。クエリは次の 3 種類のいずれかです。

  • 1 a b : G の頂点数を n としたとき、頂点 n+1 の座標を (x_{n+1},y_{n+1})=(a,b) として、G に頂点 n+1 を追加する。
  • 2 : G の頂点数を n、連結成分数を m とする。
    • m=1 のとき、-1 を出力する。
    • m\geq 2 のとき、距離が最小である連結成分をすべてマージし、その最小の距離の値を出力する。厳密には、G の連結成分を A_1,A_2,\ldots,A_m として、\displaystyle k=\min_{1\leq i\lt j\leq m} d(A_i,A_j) とする。同じ連結成分にない頂点の組 (u,v)\ (1\leq u\lt v\leq n) であって d(u,v)=k を満たすようなものすべてについて、頂点 u と v の間に辺を張る。その後、k を出力する。
  • 3 u v : 頂点 u,v が同じ連結成分にあるならば Yes を、そうでないならば No を出力する。

制約

  • 2\leq N\leq 1500
  • 1\leq Q\leq 1500
  • 0\leq x_i,y_i\leq 10^9
  • 1 種類目のクエリについて、0\leq a,b\leq 10^9
  • 3 種類目のクエリについて、そのクエリを処理する直前の G の頂点数を n としたとき、1\leq u\lt v\leq n
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。\mathrm{query}_i は i 番目に処理するクエリである。

N Q
x_1 y_1
x_2 y_2
\vdots
x_N y_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下の 3 種類のいずれかの形式で与えられる。

1 a b
2
3 u v

出力

問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。


入力例 1

4 11
3 4
3 3
7 3
2 2
3 1 2
2
3 1 2
1 6 4
2
3 2 5
2
3 2 5
2
1 2 2
2

出力例 1

No
1
Yes
2
No
3
Yes
-1
0

はじめ、頂点 1,2,3,4 はそれぞれ座標 (3,4),(3,3),(7,3),(2,2) にあります。

  • 1 番目のクエリについて、頂点 1 と 2 は連結でないため、No を出力します。
  • 2 番目のクエリについて、連結成分は 4 つあり、各連結成分に含まれる頂点集合は \lbrace 1\rbrace, \lbrace 2\rbrace, \lbrace 3\rbrace, \lbrace 4\rbrace です。異なる連結成分間の距離の最小値は 1 であり、頂点 1 と 2 の間に辺が張られます。1 を出力します。
  • 3 番目のクエリについて、頂点 1 と 2 は連結であるため、Yes を出力します。
  • 4 番目のクエリについて、座標 (6,4) に頂点 5 を追加します。
  • 5 番目のクエリについて、連結成分は 4 つあり、各連結成分に含まれる頂点集合は \lbrace 1,2\rbrace,\lbrace 3\rbrace,\lbrace 4\rbrace,\lbrace 5\rbrace です。異なる連結成分間の距離の最小値は 2 であり、頂点 2 と 4 の間および頂点 3 と 5 の間に辺が張られます。2 を出力します。
  • 6 番目のクエリについて、頂点 2 と 5 は連結でないため、No を出力します。
  • 7 番目のクエリについて、連結成分は 2 つあり、各連結成分に含まれる頂点集合は \lbrace 1,2,4\rbrace,\lbrace 3,5\rbrace です。異なる連結成分間の距離の最小値は 3 であり、頂点 1 と 5 の間に辺が張られます。3 を出力します。
  • 8 番目のクエリについて、頂点 2 と 5 は連結であるため、Yes を出力します。
  • 9 番目のクエリについて、連結成分は 1 つであるため -1 を出力します。
  • 10 番目のクエリについて、座標 (2,2) に頂点 6 を追加します。
  • 11 番目のクエリについて、連結成分は 2 つあり、各連結成分に含まれる頂点集合は \lbrace 1,2,3,4,5\rbrace,\lbrace 6\rbrace です。異なる連結成分間の距離の最小値は 0 であり、頂点 4 と 6 の間に辺が張られます。0 を出力します。

Score : 500 points

Problem Statement

There is a graph G with N vertices and 0 edges on a 2-dimensional plane. The vertices are numbered from 1 to N, and vertex i is located at coordinates (x_i,y_i).

For vertices u and v of G, the distance d(u,v) between u and v is defined as the Manhattan distance d(u,v)=|x_u-x_v|+|y_u-y_v|.

Also, for two connected components A and B of G, let V(A) and V(B) be the vertex sets of A and B, respectively. The distance d(A,B) between A and B is defined as d(A,B)=\min\lbrace d(u,v)\mid u \in V(A), v\in V(B)\rbrace.

Process Q queries as described below. Each query is one of the following three types:

  • 1 a b : Let n be the number of vertices in G. Add vertex n+1 to G with coordinates (x_{n+1},y_{n+1})=(a,b).
  • 2 : Let n be the number of vertices in G and m be the number of connected components.
    • If m=1, output -1.
    • If m\geq 2, merge all connected components with the minimum distance and output the value of that minimum distance. Formally, let the connected components of G be A_1,A_2,\ldots,A_m and let \displaystyle k=\min_{1\leq i\lt j\leq m} d(A_i,A_j). For all pairs of vertices (u,v)\ (1\leq u\lt v\leq n) that are not in the same connected component and satisfy d(u,v)=k, add an edge between vertices u and v. Then, output k.
  • 3 u v : If vertices u and v are in the same connected component, output Yes; otherwise, output No.

Constraints

  • 2\leq N\leq 1500
  • 1\leq Q\leq 1500
  • 0\leq x_i,y_i\leq 10^9
  • For queries of type 1, 0\leq a,b\leq 10^9.
  • For queries of type 3, let n be the number of vertices in G just before processing that query, then 1\leq u\lt v\leq n.
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{query}_i is the i-th query to be processed.

N Q
x_1 y_1
x_2 y_2
\vdots
x_N y_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in one of the following three formats:

1 a b
2
3 u v

Output

Output the answers to the queries separated by newlines, following the instructions in the problem statement.


Sample Input 1

4 11
3 4
3 3
7 3
2 2
3 1 2
2
3 1 2
1 6 4
2
3 2 5
2
3 2 5
2
1 2 2
2

Sample Output 1

No
1
Yes
2
No
3
Yes
-1
0

Initially, vertices 1,2,3,4 are located at coordinates (3,4),(3,3),(7,3),(2,2), respectively.

  • For the 1st query, vertices 1 and 2 are not connected, so output No.
  • For the 2nd query, there are 4 connected components, and the vertex set of each connected component is \lbrace 1\rbrace, \lbrace 2\rbrace, \lbrace 3\rbrace, \lbrace 4\rbrace. The minimum distance between different connected components is 1, and an edge is added between vertices 1 and 2. Output 1.
  • For the 3rd query, vertices 1 and 2 are connected, so output Yes.
  • For the 4th query, add vertex 5 at coordinates (6,4).
  • For the 5th query, there are 4 connected components, and the vertex set of each connected component is \lbrace 1,2\rbrace,\lbrace 3\rbrace,\lbrace 4\rbrace,\lbrace 5\rbrace. The minimum distance between different connected components is 2, and edges are added between vertices 2 and 4 and between vertices 3 and 5. Output 2.
  • For the 6th query, vertices 2 and 5 are not connected, so output No.
  • For the 7th query, there are 2 connected components, and the vertex set of each connected component is \lbrace 1,2,4\rbrace,\lbrace 3,5\rbrace. The minimum distance between different connected components is 3, and an edge is added between vertices 1 and 5. Output 3.
  • For the 8th query, vertices 2 and 5 are connected, so output Yes.
  • For the 9th query, there is 1 connected component, so output -1.
  • For the 10th query, add vertex 6 at coordinates (2,2).
  • For the 11th query, there are 2 connected components, and the vertex set of each connected component is \lbrace 1,2,3,4,5\rbrace,\lbrace 6\rbrace. The minimum distance between different connected components is 0, and an edge is added between vertices 4 and 6. Output 0.