A - 11/22 String

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

この問題における 11/22 文字列の定義は C 問題および E 問題と同じです。

文字列 T が以下の条件を全て満たすとき、T を 11/22 文字列 と呼びます。

  • |T| は奇数である。ここで、|T| は T の長さを表す。
  • 1 文字目から \frac{|T|+1}{2} - 1 文字目までが 1 である。
  • \frac{|T|+1}{2} 文字目が / である。
  • \frac{|T|+1}{2} + 1 文字目から |T| 文字目までが 2 である。

例えば 11/22, 111/222, / は 11/22 文字列ですが、1122, 1/22, 11/2222, 22/11, //2/2/211 はそうではありません。

1, 2, / からなる長さ N の文字列 S が与えられます。S が 11/22 文字列であるか判定してください。

制約

  • 1 \leq N \leq 100
  • S は 1, 2, / からなる長さ N の文字列

入力

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

N
S

出力

S が 11/22 文字列であれば Yes を、そうでなければ No を出力せよ。


入力例 1

5
11/22

出力例 1

Yes

11/22 は問題文の 11/22 文字列の条件を満たします。


入力例 2

1
/

出力例 2

Yes

/ は問題文の 11/22 文字列の条件を満たします。


入力例 3

4
1/22

出力例 3

No

1/22 は問題文の 11/22 文字列の条件を満たしません。


入力例 4

5
22/11

出力例 4

No

Score : 150 points

Problem Statement

The definition of an 11/22 string in this problem is the same as in Problems C and E.

A string T is called an 11/22 string when it satisfies all of the following conditions:

  • |T| is odd. Here, |T| denotes the length of T.
  • The 1-st through (\frac{|T|+1}{2} - 1)-th characters are all 1.
  • The (\frac{|T|+1}{2})-th character is /.
  • The (\frac{|T|+1}{2} + 1)-th through |T|-th characters are all 2.

For example, 11/22, 111/222, and / are 11/22 strings, but 1122, 1/22, 11/2222, 22/11, and //2/2/211 are not.

Given a string S of length N consisting of 1, 2, and /, determine whether S is an 11/22 string.

Constraints

  • 1 \leq N \leq 100
  • S is a string of length N consisting of 1, 2, and /.

Input

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

N
S

Output

If S is an 11/22 string, print Yes; otherwise, print No.


Sample Input 1

5
11/22

Sample Output 1

Yes

11/22 satisfies the conditions for an 11/22 string in the problem statement.


Sample Input 2

1
/

Sample Output 2

Yes

/ satisfies the conditions for an 11/22 string.


Sample Input 3

4
1/22

Sample Output 3

No

1/22 does not satisfy the conditions for an 11/22 string.


Sample Input 4

5
22/11

Sample Output 4

No
B - tcdr

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字からなる文字列 S が与えられます。
S から a, e, i, o, u をすべて取り除いて得られる文字列を出力してください。
なお、S は a, e, i, o, u 以外の文字を一つ以上含みます。

制約

  • S は英小文字からなる長さ 1 以上 100 以下の文字列
  • S は a, e, i, o, u 以外の文字を一つ以上含む

入力

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

S

出力

答えを出力せよ。


入力例 1

atcoder

出力例 1

tcdr

S = atcoder のとき、1, 4, 6 文字目を取り除いて tcdr を得ます。


入力例 2

xyz

出力例 2

xyz

入力例 3

aaaabbbbcccc

出力例 3

bbbbcccc

Score : 100 points

Problem Statement

You are given a string S consisting of lowercase English letters.
Remove all occurrences of a, e, i, o, u from S and print the resulting string.
S contains at least one character other than a, e, i, o, u.

Constraints

  • S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.
  • S contains at least one character other than a, e, i, o, u.

Input

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

S

Output

Print the answer.


Sample Input 1

atcoder

Sample Output 1

tcdr

For S = atcoder, remove the 1-st, 4-th, and 6-th characters to get tcdr.


Sample Input 2

xyz

Sample Output 2

xyz

Sample Input 3

aaaabbbbcccc

Sample Output 3

bbbbcccc
C - Full House 3

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

7 枚のカードがあります。i 番目 (i=1,\ldots,7) のカードには整数 A_i が書かれています。
これらのカードから 5 枚を選び、フルハウスとできるか判定してください。

ただし、 5 枚組のカードは以下の条件を満たすとき、またそのときに限って、フルハウスであると呼ばれます。

  • 異なる整数 x,y について、 x が書かれたカード 3 枚と y が書かれたカード 2 枚からなる。

制約

  • A_i は 1 以上 13 以下の整数

入力

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

A_1 A_2 A_3 A_4 A_5 A_6 A_7

出力

5 枚カードを選んでフルハウスとできるなら Yes 、そうでないなら No と出力せよ。


入力例 1

1 4 1 4 2 1 3

出力例 1

Yes

例えば、 (1,1,1,4,4) とカードを選択することでフルハウスとできます。


入力例 2

11 12 13 10 13 12 11

出力例 2

No

7 枚のカードからどのように 5 枚を選んでもフルハウスとはできません。


入力例 3

7 7 7 7 7 7 7

出力例 3

No

同じカード 5 枚組はフルハウスではないことに注意してください。


入力例 4

13 13 1 1 7 4 13

出力例 4

Yes

Score : 250 points

Problem Statement

We have seven cards. The i-th card (i=1,\ldots,7) has an integer A_i written on it.
Determine whether it is possible to choose five of them so that the chosen cards form a full house.

A set of five cards is called a full house if and only if the following conditions are satisfied:

  • For different integers x and y, there are three cards with x and two cards with y.

Constraints

  • A_i is an integer between 1 and 13, inclusive.

Input

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

A_1 A_2 A_3 A_4 A_5 A_6 A_7

Output

If a full house can be formed by choosing five cards, print Yes; otherwise, print No.


Sample Input 1

1 4 1 4 2 1 3

Sample Output 1

Yes

For example, by choosing the cards (1,1,1,4,4), we can form a full house.


Sample Input 2

11 12 13 10 13 12 11

Sample Output 2

No

No five cards chosen from the seven cards form a full house.


Sample Input 3

7 7 7 7 7 7 7

Sample Output 3

No

Note that five identical cards do not form a full house.


Sample Input 4

13 13 1 1 7 4 13

Sample Output 4

Yes
D - Binary Alchemy

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 種類の元素があり、元素には 1, 2, \ldots, N の番号が付けられています。

元素どうしは合成させることができ、元素 i と元素 j を合成すると i \geq j のとき元素 A_{i, j} に、i < j のとき元素 A_{j, i} に変化します。

元素 1 に対して元素 1, 2, \ldots, N をこの順に合成したとき、最終的に得られる元素を求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq A_{i, j} \leq N
  • 入力される値はすべて整数

入力

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

N
A_{1, 1}
A_{2, 1} A_{2, 2}
\vdots
A_{N, 1} A_{N, 2} \ldots A_{N, N}

出力

最終的に得られる元素の番号を出力せよ。


入力例 1

4
3
2 4
3 1 2
2 1 2 4

出力例 1

2
  • 元素 1 と元素 1 を合成すると、元素 3 が得られます。

  • 元素 3 と元素 2 を合成すると、元素 1 が得られます。

  • 元素 1 と元素 3 を合成すると、元素 3 が得られます。

  • 元素 3 と元素 4 を合成すると、元素 2 が得られます。

したがって、出力するべき値は 2 です。


入力例 2

5
5
5 5
5 5 5
5 5 5 5
5 5 5 5 5

出力例 2

5

入力例 3

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

出力例 3

5

Score : 200 points

Problem Statement

There are N types of elements numbered 1, 2, \ldots, N.

Elements can be combined with each other. When elements i and j are combined, they transform into element A_{i, j} if i \geq j, and into element A_{j, i} if i < j.

Starting with element 1, combine it with elements 1, 2, \ldots, N in this order. Find the final element obtained.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq A_{i, j} \leq N
  • All input values are integers.

Input

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

N
A_{1, 1}
A_{2, 1} A_{2, 2}
\vdots
A_{N, 1} A_{N, 2} \ldots A_{N, N}

Output

Print the number representing the final element obtained.


Sample Input 1

4
3
2 4
3 1 2
2 1 2 4

Sample Output 1

2
  • Combining element 1 with element 1 results in element 3.

  • Combining element 3 with element 2 results in element 1.

  • Combining element 1 with element 3 results in element 3.

  • Combining element 3 with element 4 results in element 2.

Therefore, the value to be printed is 2.


Sample Input 2

5
5
5 5
5 5 5
5 5 5 5
5 5 5 5 5

Sample Output 2

5

Sample Input 3

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

Sample Output 3

5
E - Paint to make a rectangle

Time Limit: 2 sec / Memory Limit: 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 - Counting 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 人の生徒からなるクラスがあり、i\,(1 \leq i \leq N) 番目の生徒の身長は A_i です。

j=1,2,\ldots,Q について、以下の質問に答えてください。

  • N 人のうち、身長が x_j 以上の生徒は何人か?

制約

  • 1 \leq N,Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq x_j \leq 10^9
  • 入力は全て整数

入力

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

N Q
A_1 A_2 \ldots A_N
x_1
x_2
\vdots
x_Q

出力

Q 行出力せよ。

j\,(1 \leq j \leq Q) 行目には身長が x_j 以上の生徒の数を出力せよ。


入力例 1

3 1
100 160 130
120

出力例 1

2

身長が 120 以上の生徒は 2 番目の生徒と 3 番目の生徒です。


入力例 2

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

出力例 2

0
1
2
3
4

入力例 3

5 5
804289384 846930887 681692778 714636916 957747794
424238336
719885387
649760493
596516650
189641422

出力例 3

5
3
5
5
5

Score : 300 points

Problem Statement

There is a class with N students. The height of the i-th student (1 \leq i \leq N) is A_i.

For each j=1,2,\ldots,Q, answer the following question.

  • How many of the N students have a height of at least x_j?

Constraints

  • 1 \leq N,Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq x_j \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
A_1 A_2 \ldots A_N
x_1
x_2
\vdots
x_Q

Output

Print Q lines.

The j-th line (1 \leq j \leq Q) should contain the number of students with a height of at least x_j.


Sample Input 1

3 1
100 160 130
120

Sample Output 1

2

The students with a height of at least 120 are the 2-nd and 3-rd ones.


Sample Input 2

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

Sample Output 2

0
1
2
3
4

Sample Input 3

5 5
804289384 846930887 681692778 714636916 957747794
424238336
719885387
649760493
596516650
189641422

Sample Output 3

5
3
5
5
5
G - Reachability Query 2

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

N 頂点 M 辺の有向グラフが与えられます。
頂点には 1 から N の番号がついており、i 番目の辺は頂点 X_i から頂点 Y_i への有向辺です。
最初全ての頂点は白色です。

Q 個のクエリが与えられるので順に処理してください。クエリは以下の 2 種類のいずれかです。

  • 1 v:頂点 v を黒色にする
  • 2 v:頂点 v から辺を辿って黒色の頂点に到達可能かどうか判定する

制約

  • 1\leq N \leq 3\times 10^5
  • 0\leq M \leq 3\times 10^5
  • 1\leq Q \leq 3\times 10^5
  • 1\leq X_i,Y_i \leq N
  • 自己辺をもたない。すなわち X_i \neq Y_i
  • 多重辺をもたない。すなわち (X_i,Y_i) は相異なる
  • クエリにおいて 1 \leq v \leq N
  • 入力は全て整数

入力

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

N M
X_1 Y_1
\vdots
X_M Y_M
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

\mathrm{query}_i は i 番目のクエリを表し、以下のいずれかの形式で与えられる。

1 v
2 v

出力

2 種類目のクエリの個数を q として q 行出力せよ。

i 行目には、i 番目の 2 種類目のクエリにおいて到達可能なら Yes、到達不可能なら No と出力せよ。


入力例 1

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

出力例 1

Yes
No
Yes
  • 最初、与えられたグラフは下図一番左の通りです。
  • 1 番目のクエリにより頂点 3 が黒色になり、下図中央のようになります。
  • 2 番目のクエリにおいて、頂点 1 から黒色の頂点 3 に到達可能です。
  • 3 番目のクエリにおいて、頂点 4 から黒色の頂点に到達することはできません。
  • 4 番目のクエリにより頂点 5 が黒色になり、下図右のようになります。
  • 5 番目のクエリにおいて、頂点 4 から黒色の頂点 5 に到達可能です。

図

Score : 425 points

Problem Statement

You are given a directed graph with N vertices and M edges.
The vertices are numbered from 1 to N, and the i-th edge is a directed edge from vertex X_i to vertex Y_i.
Initially, all vertices are white.

Process Q queries in order. Each query is of one of the following two types:

  • 1 v: Color vertex v black.
  • 2 v: Determine whether it is possible to reach a black vertex by following edges from vertex v.

Constraints

  • 1\leq N \leq 3\times 10^5
  • 0\leq M \leq 3\times 10^5
  • 1\leq Q \leq 3\times 10^5
  • 1\leq X_i,Y_i \leq N
  • There are no self-loops, that is, X_i \neq Y_i.
  • There are no multiple edges, that is, (X_i,Y_i) are distinct.
  • In queries, 1 \leq v \leq N.
  • All input values are integers.

Input

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

N M
X_1 Y_1
\vdots
X_M Y_M
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

\mathrm{query}_i represents the i-th query and is given in one of the following formats:

1 v
2 v

Output

Let q be the number of queries of the second type. Output q lines.

The i-th line should contain Yes if a black vertex is reachable in the i-th query of the second type, and No otherwise.


Sample Input 1

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

Sample Output 1

Yes
No
Yes
  • Initially, the given graph is as shown in the leftmost figure below.
  • By the first query, vertex 3 becomes black, as shown in the center figure.
  • In the second query, it is possible to reach black vertex 3 from vertex 1.
  • In the third query, it is not possible to reach a black vertex from vertex 4.
  • By the fourth query, vertex 5 becomes black, as shown in the rightmost figure.
  • In the fifth query, it is possible to reach black vertex 5 from vertex 4.

Figure

H - Throwing the Die

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

サイコロを使ったゲームをします。ゲームは最大 N 回のターンからなり、各ターンは次のように進行します。

  • 1,\ldots,6 の目が等確率で出る 6 面ダイスを振り、出目を X とする(出目は各ターンで独立とする)。
  • 現在が N ターン目なら、スコア を X とし、ゲームを終了する。
  • そうでないとき、ゲームを続行するか終了するか選択する。
    • ゲームを終了する場合、スコアを X とし、残りのターンは行わずにゲームを終了する。

スコアの期待値が最大になるように行動したとき、スコアの期待値を求めてください。

制約

  • 1 \leq N \leq 100

入力

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

N

出力

答えを出力せよ。
なお、真の解との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。


入力例 1

1

出力例 1

3.5000000000

入力例 2

2

出力例 2

4.2500000000

入力例 3

10

出力例 3

5.6502176688

Score : 500 points

Problem Statement

Let us play a game using a die. The game consists of at most N turns, each of which goes as follows.

  • Throw a 6-sided die that shows 1,\ldots,6 with equal probability, and let X be the number shown (each throw is independent of the others).
  • If it is the N-th turn now, your score is X, and the game ends.
  • Otherwise, choose whether to continue or end the game.
    • If you end the game, your score is X, and there is no more turn.

Find the expected value of your score when you play the game to maximize this expected value.

Constraints

  • 1 \leq N \leq 100

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.
Your output is considered correct if its absolute or relative error from the true answer is at most 10^{-6}.


Sample Input 1

1

Sample Output 1

3.5000000000

Sample Input 2

2

Sample Output 2

4.2500000000

Sample Input 3

10

Sample Output 3

5.6502176688
I - Add One Edge 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 頂点の木が与えられます。i 番目の辺 (1\leq i\leq N-1) は頂点 u_i と頂点 v_i を双方向に結んでいます。

与えられた木に無向辺を一本追加して得られるグラフは、必ずちょうど一つの閉路を含みます。

そのようなグラフのうち、以下の条件を全て満たすものの個数を求めてください。

  • グラフは単純グラフ
  • グラフの閉路に含まれる頂点の次数は全て 3

制約

  • 3 \leq N \leq 2 \times 10^5
  • 1\leq u_i,v_i\leq N
  • 与えられるグラフは木である
  • 入力される数値は全て整数

入力

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

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

出力

答えを出力せよ。


入力例 1

6
1 2
2 3
3 4
4 5
3 6

出力例 1

1

頂点 2 と頂点 4 を結ぶ辺を追加して得られるグラフは単純グラフであり、閉路に含まれる頂点の次数は全て 3 なので条件を満たします。


入力例 2

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

出力例 2

0

条件を満たすグラフが存在しない場合もあります。


入力例 3

15
1 15
11 14
2 10
1 7
9 8
6 9
4 12
14 5
4 9
8 11
7 4
1 13
3 6
11 10

出力例 3

6

Score : 500 points

Problem Statement

You are given a tree with N vertices. The i-th edge (1 \leq i \leq N-1) connects vertices u_i and v_i bidirectionally.

Adding one undirected edge to the given tree always yields a graph with exactly one cycle.

Among such graphs, how many satisfy all of the following conditions?

  • The graph is simple.
  • All vertices in the cycle have degree 3.

Constraints

  • 3 \leq N \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N
  • The given graph is a tree.
  • All input values are integers.

Input

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

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

Output

Print the answer.


Sample Input 1

6
1 2
2 3
3 4
4 5
3 6

Sample Output 1

1

Adding an edge connecting vertices 2 and 4 yields a simple graph where all vertices in the cycle have degree 3, so it satisfies the conditions.


Sample Input 2

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

Sample Output 2

0

There are cases where no graphs satisfy the conditions.


Sample Input 3

15
1 15
11 14
2 10
1 7
9 8
6 9
4 12
14 5
4 9
8 11
7 4
1 13
3 6
11 10

Sample Output 3

6