A - Adjacent Squares

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

縦 H 行、横 W 列のマス目があり、このうち上から i 個目、左から j 個目のマスを (i,j) と呼びます。
このとき、マス (R,C) に辺で隣接するマスの個数を求めてください。

ただし、ある 2 つのマス (a,b),(c,d) が辺で隣接するとは、 |a-c|+|b-d|=1 (|x| を x の絶対値とする) であることを言います。

制約

  • 入力は全て整数
  • 1 \le R \le H \le 10
  • 1 \le C \le W \le 10

入力

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

H W
R C

出力

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


入力例 1

3 4
2 2

出力例 1

4

入出力例 1,2,3 に対する説明は、出力例 3 の下にまとめて示します。


入力例 2

3 4
1 3

出力例 2

3

入力例 3

3 4
3 4

出力例 3

2

H=3,W=4 のとき、マス目は以下のようになります。

  • 入力例 1 について、マス (2,2) に隣接するマスは 4 つです。
  • 入力例 2 について、マス (1,3) に隣接するマスは 3 つです。
  • 入力例 3 について、マス (3,4) に隣接するマスは 2 つです。


入力例 4

1 10
1 5

出力例 4

2

入力例 5

8 1
8 1

出力例 5

1

入力例 6

1 1
1 1

出力例 6

0

Score : 100 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left.
Find the number of squares that share a side with Square (R, C).

Here, two squares (a,b) and (c,d) are said to share a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Constraints

  • All values in input are integers.
  • 1 \le R \le H \le 10
  • 1 \le C \le W \le 10

Input

Input is given from Standard Input in the following format:

H W
R C

Output

Print the answer as an integer.


Sample Input 1

3 4
2 2

Sample Output 1

4

We will describe Sample Inputs/Outputs 1,2, and 3 at once below Sample Output 3.


Sample Input 2

3 4
1 3

Sample Output 2

3

Sample Input 3

3 4
3 4

Sample Output 3

2

When H=3 and W=4, the grid looks as follows.

  • For Sample Input 1, there are 4 squares adjacent to Square (2,2).
  • For Sample Input 2, there are 3 squares adjacent to Square (1,3).
  • For Sample Input 3, there are 2 squares adjacent to Square (3,4).


Sample Input 4

1 10
1 5

Sample Output 4

2

Sample Input 5

8 1
8 1

Sample Output 5

1

Sample Input 6

1 1
1 1

Sample Output 6

0
B - Zero Sum Game

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1 から N の番号が付けられた N 人の人がおり、この中で一対一の勝敗のつくゲームを何度か行いました。N 人は最初にそれぞれ持ち点として 0 を持っており、各ゲームでは勝者の持ち点が 1 増え、敗者の持ち点が 1 減ります(持ち点が負になることもあります)。最終的に人 i\ (1\leq i\leq N-1) の持ち点が A_i になったとき、人 N の持ち点を求めてください。なお、ゲームの進行によらず最終的な人 N の持ち点は一意に定まることが示せます。

制約

  • 2\leq N\leq 100
  • -100\leq A_i\leq 100
  • 入力は全て整数

入力

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

N
A_1 A_2 \ldots A_{N-1}

出力

答えを出力せよ。


入力例 1

4
1 -2 -1

出力例 1

2

最終的に人 1,2,3 の持ち点が 1,-2,-1 となるような進行として、例えば次のようなものが考えられます。

  • 最初、人 1,2,3,4 の持ち点はそれぞれ 0,0,0,0 である。
  • 人 1 と 2 が対戦して、人 1 が勝利する。4 人の持ち点はそれぞれ 1,-1,0,0 である。
  • 人 1 と 4 が対戦して、人 4 が勝利する。4 人の持ち点はそれぞれ 0,-1,0,1 である。
  • 人 1 と 2 が対戦して、人 1 が勝利する。4 人の持ち点はそれぞれ 1,-2,0,1 である。
  • 人 2 と 3 が対戦して、人 2 が勝利する。4 人の持ち点はそれぞれ 1,-1,-1,1 である。
  • 人 2 と 4 が対戦して、人 4 が勝利する。4 人の持ち点はそれぞれ 1,-2,-1,2 である。

この場合、人 4 の持ち点は 2 になります。ほかにも別の進行が考えられますが、どのような進行であっても人 4 の持ち点は 2 になります。


入力例 2

3
0 0

出力例 2

0

入力例 3

6
10 20 30 40 50

出力例 3

-150

Score: 100 points

Problem Statement

There are N people labeled 1 to N, who have played several one-on-one games without draws. Initially, each person started with 0 points. In each game, the winner's score increased by 1 and the loser's score decreased by 1 (scores can become negative). Determine the final score of person N if the final score of person i\ (1\leq i\leq N-1) is A_i. It can be shown that the final score of person N is uniquely determined regardless of the sequence of games.

Constraints

  • 2 \leq N \leq 100
  • -100 \leq A_i \leq 100
  • All input values are integers.

Input

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

N
A_1 A_2 \ldots A_{N-1}

Output

Print the answer.


Sample Input 1

4
1 -2 -1

Sample Output 1

2

Here is one possible sequence of games where the final scores of persons 1, 2, 3 are 1, -2, -1, respectively.

  • Initially, persons 1, 2, 3, 4 have 0, 0, 0, 0 points, respectively.
  • Persons 1 and 2 play, and person 1 wins. The players now have 1, -1, 0, 0 point(s).
  • Persons 1 and 4 play, and person 4 wins. The players now have 0, -1, 0, 1 point(s).
  • Persons 1 and 2 play, and person 1 wins. The players now have 1, -2, 0, 1 point(s).
  • Persons 2 and 3 play, and person 2 wins. The players now have 1, -1, -1, 1 point(s).
  • Persons 2 and 4 play, and person 4 wins. The players now have 1, -2, -1, 2 point(s).

In this case, the final score of person 4 is 2. Other possible sequences of games exist, but the score of person 4 will always be 2 regardless of the progression.


Sample Input 2

3
0 0

Sample Output 2

0

Sample Input 3

6
10 20 30 40 50

Sample Output 3

-150
C - 1122 String

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

文字列 T が以下の 3 つの条件をすべてみたすとき、かつそのときに限り、T を 1122 文字列 と呼びます。

  • \lvert T \rvert は偶数である。ここで、\lvert T \rvert は T の長さを表す。
  • 1\leq i\leq \frac{\lvert T \rvert}{2} をみたす整数 i について、T の (2i-1) 文字目と 2i 文字目は等しい。
  • 各文字は T にちょうど 0 個または 2 個現れる。すなわち、T に含まれる文字は T にちょうど 2 回ずつ登場する。

英小文字のみからなる文字列 S が与えられるので、S が 1122 文字列であるならば Yes を、そうでないならば No を出力してください。

制約

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

入力

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

S

出力

S が 1122 文字列ならば Yes を、そうでないならば No を出力せよ。


入力例 1

aabbcc

出力例 1

Yes

S=aabbcc は 1122 文字列の条件をすべてみたしているため、Yes を出力します。


入力例 2

aab

出力例 2

No

S=aab は長さが奇数であり、 1 つめの条件をみたしていないため、No を出力します。


入力例 3

zzzzzz

出力例 3

No

S=zzzzzz は z が 6 個含まれており、 3 つめの条件をみたしていないため、No を出力します。

Score : 150 points

Problem Statement

A string T is called a 1122 string if and only if it satisfies all of the following three conditions:

  • \lvert T \rvert is even. Here, \lvert T \rvert denotes the length of T.
  • For each integer i satisfying 1\leq i\leq \frac{|T|}{2}, the (2i-1)-th and 2i-th characters of T are equal.
  • Each character appears in T exactly zero or two times. That is, every character contained in T appears exactly twice in T.

Given a string S consisting of lowercase English letters, print Yes if S is a 1122 string, and No otherwise.

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

If S is a 1122 string, print Yes; otherwise, print No.


Sample Input 1

aabbcc

Sample Output 1

Yes

S=aabbcc satisfies all the conditions for a 1122 string, so print Yes.


Sample Input 2

aab

Sample Output 2

No

S=aab has an odd length and does not satisfy the first condition, so print No.


Sample Input 3

zzzzzz

Sample Output 3

No

S=zzzzzz contains six zs and does not satisfy the third condition, so print No.


D - Rotate

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 行 N 列のマス目が与えられます。上から i 行目、左から j 列目のマスには整数 A_{i,j} が書かれています。ここで、A_{i,j} は 0 か 1 であることが保証されます。

マス目の外側のマスに書かれた整数を時計回りに 1 個ずつずらしたときのマス目を出力してください。

ただし外側のマスとは、1 行目、N 行目、1 列目、N 列目のいずれか 1 つ以上に属するマスの集合のことを指します。

制約

  • 2 \le N \le 100
  • 0 \le A_{i,j} \le 1(1 \le i,j \le N)
  • 入力は全て整数

入力

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

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

出力

マス目の外側のマスに書かれた整数を時計回りに 1 個ずつずらしたときのマス目において、上から i 行目、左から j 列目のマスに書かれている整数を B_{i,j} と置く。このとき、以下の形式で出力せよ。

B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

入力例 1

4
0101
1101
1111
0000

出力例 1

1010
1101
0111
0001

上から i 行目、左から j 列目のマスを (i,j) と呼ぶこととします。

外側のマスは (1,1) から時計回りに列挙すると (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1),(2,1) の 12 個です。

これらのマスに書かれている整数を、時計回りに 1 個ずつ動かすと出力欄のようになります。


入力例 2

2
11
11

出力例 2

11
11

入力例 3

5
01010
01001
10110
00110
01010

出力例 3

00101
11000
00111
00110
10100

Score : 200 points

Problem Statement

You are given a grid with N rows and N columns. An integer A_{i, j} is written on the square at the i-th row from the top and j-th column from the left. Here, it is guaranteed that A_{i,j} is either 0 or 1.

Shift the integers written on the outer squares clockwise by one square each, and print the resulting grid.

Here, the outer squares are those in at least one of the 1-st row, N-th row, 1-st column, and N-th column.

Constraints

  • 2 \le N \le 100
  • 0 \le A_{i,j} \le 1(1 \le i,j \le N)
  • All input values are integers.

Input

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

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

Output

Let B_{i,j} be the integer written on the square at the i-th row from the top and j-th column from the left in the grid resulting from shifting the outer squares clockwise by one square each. Print them in the following format:

B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

Sample Input 1

4
0101
1101
1111
0000

Sample Output 1

1010
1101
0111
0001

We denote by (i,j) the square at the i-th row from the top and j-th column from the left.

The outer squares, in clockwise order starting from (1,1), are the following 12 squares: (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1), and (2,1).

The sample output shows the resulting grid after shifting the integers written on those squares clockwise by one square.


Sample Input 2

2
11
11

Sample Output 2

11
11

Sample Input 3

5
01010
01001
10110
00110
01010

Sample Output 3

00101
11000
00111
00110
10100
E - Even Digits

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

非負整数 n が次の条件を満たすとき、n を 良い整数 と呼びます。

  • n を 10 進法で表したときに、偶数の数字 (0, 2, 4, 6, 8) のみが登場する。

例えば 0、68 および 2024 は良い整数です。

整数 N が与えられます。良い整数のうち小さい方から N 番目の整数を求めてください。

制約

  • 1 \leq N \leq 10^{12}
  • N は整数

入力

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

N

出力

小さい方から N 番目の良い整数を出力せよ。


入力例 1

8

出力例 1

24

良い整数を小さい方から順に並べると 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, \dots となります。
小さい方から 8 番目の良い整数は 24 なので、これを出力します。


入力例 2

133

出力例 2

2024

入力例 3

31415926535

出力例 3

2006628868244228

Score: 300 points

Problem Statement

A non-negative integer n is called a good integer when it satisfies the following condition:

  • All digits in the decimal notation of n are even numbers (0, 2, 4, 6, and 8).

For example, 0, 68, and 2024 are good integers.

You are given an integer N. Find the N-th smallest good integer.

Constraints

  • 1 \leq N \leq 10^{12}
  • N is an integer.

Input

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

N

Output

Print the N-th smallest good integer.


Sample Input 1

8

Sample Output 1

24

The good integers in ascending order are 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, \dots.
The eighth smallest is 24, which should be printed.


Sample Input 2

133

Sample Output 2

2024

Sample Input 3

31415926535

Sample Output 3

2006628868244228
F - A+B+C

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

3 個の数列 A=(A_1,\ldots,A_N), B=(B_1,\ldots,B_M), C=(C_1,\ldots,C_L) が与えられます。

さらに数列 X=(X_1,\ldots,X_Q) が与えられるので、各 i=1,\ldots,Q に対して次の問題を解いてください。

問題:A,B,C からそれぞれ 1 個ずつ要素を選び、和を X_i にすることができるか?

制約

  • 1 \leq N,M,L \leq 100
  • 0 \leq A_i, B_i ,C_i \leq 10^8
  • 1 \leq Q \leq 2\times 10^5
  • 0 \leq X_i \leq 3\times 10^8
  • 入力は全て整数である

入力

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

N
A_1 \ldots A_N
M
B_1 \ldots B_M
L
C_1 \ldots C_L
Q
X_1 \ldots X_Q

出力

Q 行出力せよ。
i 行目には、A,B,C からそれぞれ 1 個ずつ要素を選び和を X_i にすることができるならば Yes、できないならば No と出力せよ。


入力例 1

3
1 2 3
2
2 4
6
1 2 4 8 16 32
4
1 5 10 50

出力例 1

No
Yes
Yes
No
  • A,B,C からそれぞれ 1 個ずつ要素を選び和を 1 にすることはできません。
  • A,B,C からそれぞれ 1,2,2 を選ぶと和を 5 にすることができます。
  • A,B,C からそれぞれ 2,4,4 を選ぶと和を 10 にすることができます。
  • A,B,C からそれぞれ 1 個ずつ要素を選び和を 50 にすることはできません。

Score: 250 points

Problem Statement

You are given three sequences A=(A_1,\ldots,A_N), B=(B_1,\ldots,B_M), and C=(C_1,\ldots,C_L).

Additionally, a sequence X=(X_1,\ldots,X_Q) is given. For each i=1,\ldots,Q, solve the following problem:

Problem: Is it possible to select one element from each of A, B, and C so that their sum is X_i?

Constraints

  • 1 \leq N,M,L \leq 100
  • 0 \leq A_i, B_i ,C_i \leq 10^8
  • 1 \leq Q \leq 2\times 10^5
  • 0 \leq X_i \leq 3\times 10^8
  • All input values are integers.

Input

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

N
A_1 \ldots A_N
M
B_1 \ldots B_M
L 
C_1 \ldots C_L
Q
X_1 \ldots X_Q

Output

Print Q lines. The i-th line should contain Yes if it is possible to select one element from each of A, B, and C so that their sum is X_i, and No otherwise.


Sample Input 1

3
1 2 3
2
2 4
6
1 2 4 8 16 32
4
1 5 10 50

Sample Output 1

No
Yes
Yes
No
  • It is impossible to select one element from each of A, B, and C so that their sum is 1.
  • Selecting 1, 2, and 2 from A, B, and C, respectively, makes the sum 5.
  • Selecting 2, 4, and 4 from A, B, and C, respectively, makes the sum 10.
  • It is impossible to select one element from each of A, B, and C so that their sum is 50.
G - ABC Transform

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

A, B, C のみからなる文字列 S が与えられます。

S^{(0)}:=S とし、i=1,2,3,\ldots について S^{(i)} を S^{(i-1)} の各文字を A → BC, B → CA, C → AB と同時に置き換えたものと定義します。

以下の Q 個のクエリに答えてください。i 個目のクエリの内容は以下の通りです。

  • S^{(t_i)} の先頭から k_i 文字目を出力せよ。

制約

  • S は A, B, C のみからなる長さ 1 以上 10^5 以下の文字列
  • 1 \leq Q \leq 10^5
  • 0 \leq t_i \leq 10^{18}
  • 1 \leq k_i \leq \min(10^{18},\ S^{(t_i)} の長さ)
  • Q, t_i, k_i は整数

入力

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

S
Q
t_1 k_1
t_2 k_2
\hspace{0.4cm}\vdots
t_Q k_Q

出力

Q 個のクエリを添字の昇順に、すなわち与えられる順に処理し、出力ごとに改行せよ。


入力例 1

ABC
4
0 1
1 1
1 3
1 6

出力例 1

A
B
C
B

S^{(0)}=ABC, S^{(1)}=BCCAAB です。

よって各クエリへの答えは順に A, B, C, B となります。


入力例 2

CBBAACCCCC
5
57530144230160008 659279164847814847
29622990657296329 861239705300265164
509705228051901259 994708708957785197
176678501072691541 655134104344481648
827291290937314275 407121144297426665

出力例 2

A
A
C
A
A

Score : 400 points

Problem Statement

You are given a string S consisting of A, B, C.

Let S^{(0)}:=S. For i=1,2,3,\ldots, let S^{(i)} be the result of simultaneously replacing the characters of S^{(i-1)} as follows: A → BC, B → CA, C → AB.

Answer Q queries. The i-th query is as follows.

  • Print the k_i-th character from the beginning of S^{(t_i)}.

Constraints

  • S is a string of length between 1 and 10^5 (inclusive) consisting of A, B, C.
  • 1 \leq Q \leq 10^5
  • 0 \leq t_i \leq 10^{18}
  • 1 \leq k_i \leq \min(10^{18}, the length of S^{(t_i)})
  • Q, t_i, k_i are integers.

Input

Input is given from Standard Input in the following format:

S
Q
t_1 k_1
t_2 k_2
\hspace{0.4cm}\vdots
t_Q k_Q

Output

Process the Q queries in ascending order of index, that is, in the given order. Each answer should be followed by a newline.


Sample Input 1

ABC
4
0 1
1 1
1 3
1 6

Sample Output 1

A
B
C
B

We have S^{(0)}=ABC, S^{(1)}=BCCAAB.

Thus, the answers to the queries are A, B, C, B in the given order.


Sample Input 2

CBBAACCCCC
5
57530144230160008 659279164847814847
29622990657296329 861239705300265164
509705228051901259 994708708957785197
176678501072691541 655134104344481648
827291290937314275 407121144297426665

Sample Output 2

A
A
C
A
A
H - Graph Destruction

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 頂点 M 辺の単純な無向グラフが与えられます。
辺 i は、頂点 A_i と B_i を結んでいます。

頂点 1,2,\ldots,N を順番に消していきます。
なお、頂点 i を消すとは、頂点 i と、頂点 i に接続する全ての辺をグラフから削除することです。

i=1,2,\ldots,N について、頂点 i まで消した時にグラフはいくつの連結成分に分かれていますか?

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq \min(\frac{N(N-1)}{2} , 2 \times 10^5 )
  • 1 \leq A_i \lt B_i \leq N
  • i \neq j ならば (A_i,B_i) \neq (A_j,B_j)
  • 入力は全て整数である

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

N 行出力せよ。
i 行目には、頂点 i まで消した時のグラフの連結成分の数を出力せよ。


入力例 1

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

出力例 1

1
2
3
2
1
0


グラフは上図のように変化していきます。


入力例 2

8 7
7 8
3 4
5 6
5 7
5 8
6 7
6 8

出力例 2

3
2
2
1
1
1
1
0

はじめからグラフが非連結なこともあります。

Score : 500 points

Problem Statement

Given is an undirected graph with N vertices and M edges.
Edge i connects Vertices A_i and B_i.

We will erase Vertices 1, 2, \ldots, N one by one.
Here, erasing Vertex i means deleting Vertex i and all edges incident to Vertex i from the graph.

For each i=1, 2, \ldots, N, how many connected components does the graph have when vertices up to Vertex i are deleted?

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq \min(\frac{N(N-1)}{2} , 2 \times 10^5 )
  • 1 \leq A_i \lt B_i \leq N
  • (A_i,B_i) \neq (A_j,B_j) if i \neq j.
  • All values in input are integers.

Input

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 N lines.
The i-th line should contain the number of connected components in the graph when vertices up to Vertex i are deleted.


Sample Input 1

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

Sample Output 1

1
2
3
2
1
0


The figure above shows the transition of the graph.


Sample Input 2

8 7
7 8
3 4
5 6
5 7
5 8
6 7
6 8

Sample Output 2

3
2
2
1
1
1
1
0

The graph may be disconnected from the beginning.

I - Alkane

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 頂点の無向木 T が与えられます。頂点には 1, 2, \ldots, N の番号が付いており、i 番目の辺は頂点 A_i と頂点 B_i を結ぶ無向辺です。

グラフがアルカンであるとは以下の条件をともに満たしていることであると定義します。

  • グラフは無向木である
  • すべての頂点の次数が 1 または 4 であり、次数 4 の頂点が 1 つ以上存在する

T の部分グラフであってアルカンであるものが存在するか判定し、存在する場合はそのようなものの頂点数の最大値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • 与えられるグラフは無向木
  • 入力される値はすべて整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_{N - 1} B_{N - 1}

出力

T の部分グラフであってアルカンであるものが存在する場合はそのようなものの頂点数の最大値を出力せよ。そうでない場合は -1 と出力せよ。


入力例 1

9
1 2
2 3
3 4
4 5
2 6
2 7
3 8
3 9

出力例 1

8

頂点 u と頂点 v を結ぶ無向辺を辺 (u, v) と表記します。

頂点 1,2,3,4,6,7,8,9、辺 (1,2),(2,3),(3,4),(2,6),(2,7),(3,8),(3,9) からなる部分グラフはアルカンです。


入力例 2

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

出力例 2

-1

入力例 3

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

出力例 3

11

Score : 500 points

Problem Statement

You are given an undirected tree T with N vertices, numbered 1, 2, \ldots, N. The i-th edge is an undirected edge connecting vertices A_i and B_i.

A graph is defined to be an alkane if and only if it satisfies the following conditions:

  • The graph is an undirected tree.
  • Every vertex has degree 1 or 4, and there is at least one vertex of degree 4.

Determine whether there exists a subgraph of T that is an alkane, and if so, find the maximum number of vertices in such a subgraph.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • The given graph is an undirected tree.
  • All input values are integers.

Input

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

N
A_1 B_1
A_2 B_2
\vdots
A_{N - 1} B_{N - 1}

Output

If there exists a subgraph of T that is an alkane, print the maximum number of vertices in such a subgraph. Otherwise, print -1.


Sample Input 1

9
1 2
2 3
3 4
4 5
2 6
2 7
3 8
3 9

Sample Output 1

8

Let (u, v) denote an undirected edge between vertices u and v.

A subgraph consisting of vertices 1,2,3,4,6,7,8,9 and edges (1,2),(2,3),(3,4),(2,6),(2,7),(3,8),(3,9) is an alkane.


Sample Input 2

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

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

11