CodeEff/ECCO huggingface dataset:
Problem Description: Score : 300 points
Problem Statement
We have
N
clocks. The hand of the
i
-th clock
(1≤i≤N)
rotates through
360°
in exactly
T_i
seconds.
Initially, the hand of every clock stands still, pointing directly upward.
Now, Dolphin starts all the clocks simultaneously.
In how many seconds will the hand of every clock point directly upward again?
Constraints
1≤N≤100
1≤T_i≤10^{18}
All input values are integers.
The correct answer is at most
10^{18}
seconds.
Input
Input is given from Standard Input in the following format:
N
T_1
:
T_N
Output
Print the number of seconds after which the hand of every clock point directly upward again.
Sample Input 1
2
2
3
Sample Output 1
6
We have two clocks. The time when the hand of each clock points upward is as follows:
Clock
1
:
2
,
4
,
6
,
...
seconds after the beginning
Clock
2
:
3
,
6
,
9
,
...
seconds after the beginning
Therefore, it takes
6
seconds until the hands of both clocks point directly upward.
Sample Input 2
5
2
5
10
1000000000000000000
1000000000000000000
Sample Output 2
1000000000000000000
Problem Description: Score : 400 points
Problem Statement
You are given a tree with
N
vertices.
Here, a
tree
is a kind of graph, and more specifically, a connected undirected graph with
N-1
edges, where
N
is the number of its vertices.
The
i
-th edge
(1≤i≤N-1)
connects Vertices
a_i
and
b_i
, and has a length of
c_i
.
You are also given
Q
queries and an integer
K
. In the
j
-th query
(1≤j≤Q)
:
find the length of the shortest path from Vertex
x_j
and Vertex
y_j
via Vertex
K
.
Constraints
3≤N≤10^5
1≤a_i,b_i≤N (1≤i≤N-1)
1≤c_i≤10^9 (1≤i≤N-1)
The given graph is a tree.
1≤Q≤10^5
1≤K≤N
1≤x_j,y_j≤N (1≤j≤Q)
x_j≠y_j (1≤j≤Q)
x_j≠K,y_j≠K (1≤j≤Q)
Input
Input is given from Standard Input in the following format:
N
a_1
b_1
c_1
:
a_{N-1}
b_{N-1}
c_{N-1}
Q
K
x_1
y_1
:
x_{Q}
y_{Q}
Output
Print the responses to the queries in
Q
lines.
In the
j
-th line
j(1≤j≤Q)
, print the response to the
j
-th query.
Sample Input 1
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5
Sample Output 1
3
2
4
The shortest paths for the three queries are as follows:
Query
1
: Vertex
2
→ Vertex
1
→ Vertex
2
→ Vertex
4
: Length
1+1+1=3
Query
2
: Vertex
2
→ Vertex
1
→ Vertex
3
: Length
1+1=2
Query
3
: Vertex
4
→ Vertex
2
→ Vertex
1
→ Vertex
3
→ Vertex
5
: Length
1+1+1+1=4
Sample Input 2
7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7
Sample Output 2
5
14
22
The path for each query must pass Vertex
K=2
.
Sample Input 3
10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10
Sample Output 3
17000000000
Problem Description: Score : 100 points
Problem Statement
In
K-city
, there are
n
streets running east-west, and
m
streets running north-south. Each street running east-west and each street running north-south cross each other. We will call the smallest area that is surrounded by four streets a block. How many blocks there are in K-city?
Constraints
2 ≤ n, m ≤ 100
Input
Input is given from Standard Input in the following format:
n
m
Output
Print the number of blocks in K-city.
Sample Input 1
3 4
Sample Output 1
6
There are six blocks, as shown below:
Sample Input 2
2 2
Sample Output 2
1
There are one block, as shown below:
Problem Description: Score : 200 points
Problem Statement
The word
internationalization
is sometimes abbreviated to
i18n
.
This comes from the fact that there are
18
letters between the first
i
and the last
n
.
You are given a string
s
of length at least
3
consisting of lowercase English letters.
Abbreviate
s
in the same way.
Constraints
3 ≤ |s| ≤ 100
(
|s|
denotes the length of
s
.)
s
consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
s
Output
Print the abbreviation of
s
.
Sample Input 1
internationalization
Sample Output 1
i18n
Sample Input 2
smiles
Sample Output 2
s4s
Sample Input 3
xyz
Sample Output 3
x1z
Problem Description: Score : 400 points
Problem Statement
We have a sequence of length
N
,
a = (a_1, a_2, ..., a_N)
.
Each
a_i
is a positive integer.
Snuke's objective is to permute the element in
a
so that the following condition is satisfied:
For each
1 ≤ i ≤ N - 1
, the product of
a_i
and
a_{i + 1}
is a multiple of
4
.
Determine whether Snuke can achieve his objective.
Constraints
2 ≤ N ≤ 10^5
a_i
is an integer.
1 ≤ a_i ≤ 10^9
Input
Input is given from Standard Input in the following format:
N
a_1
a_2
...
a_N
Output
If Snuke can achieve his objective, print
Yes
; otherwise, print
No
.
Sample Input 1
3
1 10 100
Sample Output 1
Yes
One solution is
(1, 100, 10)
.
Sample Input 2
4
1 2 3 4
Sample Output 2
No
It is impossible to permute
a
so that the condition is satisfied.
Sample Input 3
3
1 4 1
Sample Output 3
Yes
The condition is already satisfied initially.
Sample Input 4
2
1 1
Sample Output 4
No
Sample Input 5
6
2 7 1 8 2 8
Sample Output 5
Yes
Problem Description: Score : 800 points
Problem Statement
Let
N
be a positive even number.
We have a permutation of
(1, 2, ..., N)
,
p = (p_1, p_2, ..., p_N)
.
Snuke is constructing another permutation of
(1, 2, ..., N)
,
q
, following the procedure below.
First, let
q
be an empty sequence.
Then, perform the following operation until
p
becomes empty:
Select two adjacent elements in
p
, and call them
x
and
y
in order. Remove
x
and
y
from
p
(reducing the length of
p
by
2
), and insert
x
and
y
, preserving the original order, at the beginning of
q
.
When
p
becomes empty,
q
will be a permutation of
(1, 2, ..., N)
.
Find the lexicographically smallest permutation that can be obtained as
q
.
Constraints
N
is an even number.
2 ≤ N ≤ 2 × 10^5
p
is a permutation of
(1, 2, ..., N)
.
Input
Input is given from Standard Input in the following format:
N
p_1
p_2
...
p_N
Output
Print the lexicographically smallest permutation, with spaces in between.
Sample Input 1
4
3 2 4 1
Sample Output 1
3 1 2 4
The solution above is obtained as follows:
p
q
(3, 2, 4, 1)
()
↓
↓
(3, 1)
(2, 4)
↓
↓
()
(3, 1, 2, 4)
Sample Input 2
2
1 2
Sample Output 2
1 2
Sample Input 3
8
4 6 3 2 8 5 7 1
Sample Output 3
3 1 2 7 4 6 8 5
The solution above is obtained as follows:
p
q
(4, 6, 3, 2, 8, 5, 7, 1)
()
↓
↓
(4, 6, 3, 2, 7, 1)
(8, 5)
↓
↓
(3, 2, 7, 1)
(4, 6, 8, 5)
↓
↓
(3, 1)
(2, 7, 4, 6, 8, 5)
↓
↓
()
(3, 1, 2, 7, 4, 6, 8, 5)
Problem Description: Score : 300 points
Problem Statement
In Takahashi Kingdom, there is an archipelago of
N
islands, called Takahashi Islands.
For convenience, we will call them Island
1
, Island
2
, ..., Island
N
.
There are
M
kinds of regular boat services between these islands.
Each service connects two islands. The
i
-th service connects Island
a_i
and Island
b_i
.
Cat Snuke is on Island
1
now, and wants to go to Island
N
.
However, it turned out that there is no boat service from Island
1
to Island
N
, so he wants to know whether it is possible to go to Island
N
by using two boat services.
Help him.
Constraints
3 ≤ N ≤ 200
000
1 ≤ M ≤ 200
000
1 ≤ a_i < b_i ≤ N
(a_i, b_i) \neq (1, N)
If
i \neq j
,
(a_i, b_i) \neq (a_j, b_j)
.
Input
Input is given from Standard Input in the following format:
N
M
a_1
b_1
a_2
b_2
:
a_M
b_M
Output
If it is possible to go to Island
N
by using two boat services, print
POSSIBLE
; otherwise, print
IMPOSSIBLE
.
Sample Input 1
3 2
1 2
2 3
Sample Output 1
POSSIBLE
Sample Input 2
4 3
1 2
2 3
3 4
Sample Output 2
IMPOSSIBLE
You have to use three boat services to get to Island
4
.
Sample Input 3
100000 1
1 99999
Sample Output 3
IMPOSSIBLE
Sample Input 4
5 5
1 3
4 5
2 3
2 4
1 4
Sample Output 4
POSSIBLE
You can get to Island
5
by using two boat services: Island
1
-> Island
4
-> Island
5
.
Problem Description: Score : 600 points
Problem Statement
We have a sequence of length
N
consisting of non-negative integers. Consider performing the following operation on this sequence until the largest element in this sequence becomes
N-1
or smaller. (The operation is the same as the one in Problem D.)
Determine the largest element in the sequence (if there is more than one, choose one). Decrease the value of this element by
N
, and increase each of the other elements by
1
.
It can be proved that the largest element in the sequence becomes
N-1
or smaller after a finite number of operations.
You are given the sequence
a_i
. Find the number of times we will perform the above operation.
Constraints
2 ≤ N ≤ 50
0 ≤ a_i ≤ 10^{16} + 1000
Input
Input is given from Standard Input in the following format:
N
a_1
a_2
...
a_N
Output
Print the number of times the operation will be performed.
Sample Input 1
4
3 3 3 3
Sample Output 1
0
Sample Input 2
3
1 0 3
Sample Output 2
1
Sample Input 3
2
2 2
Sample Output 3
2
Sample Input 4
7
27 0 0 0 0 0 0
Sample Output 4
3
Sample Input 5
10
1000 193 256 777 0 1 1192 1234567891011 48 425
Sample Output 5
1234567894848
Problem Description: Score : 300 points
Problem Statement
There is a box containing
N
balls. The
i
-th ball has the integer
A_i
written on it.
Snuke can perform the following operation any number of times:
Take out two balls from the box. Then, return them to the box along with a new ball, on which the absolute difference of the integers written on the two balls is written.
Determine whether it is possible for Snuke to reach the state where the box contains a ball on which the integer
K
is written.
Constraints
1 \leq N \leq 10^5
1 \leq A_i \leq 10^9
1 \leq K \leq 10^9
All input values are integers.
Input
Input is given from Standard Input in the following format:
N
K
A_1
A_2
...
A_N
Output
If it is possible for Snuke to reach the state where the box contains a ball on which the integer
K
is written, print
POSSIBLE
; if it is not possible, print
IMPOSSIBLE
.
Sample Input 1
3 7
9 3 4
Sample Output 1
POSSIBLE
First, take out the two balls
9
and
4
, and return them back along with a new ball,
abs(9-4)=5
.
Next, take out
3
and
5
, and return them back along with
abs(3-5)=2
.
Finally, take out
9
and
2
, and return them back along with
abs(9-2)=7
.
Now we have
7
in the box, and the answer is therefore
POSSIBLE
.
Sample Input 2
3 5
6 9 3
Sample Output 2
IMPOSSIBLE
No matter what we do, it is not possible to have
5
in the box. The answer is therefore
IMPOSSIBLE
.
Sample Input 3
4 11
11 3 7 15
Sample Output 3
POSSIBLE
The box already contains
11
before we do anything. The answer is therefore
POSSIBLE
.
Sample Input 4
5 12
10 2 8 6 4
Sample Output 4
IMPOSSIBLE
Problem Description: Score : 700 points
Problem Statement
Takahashi is hosting an sports meet.
There are
N
people who will participate. These people are conveniently numbered
1
through
N
.
Also, there are
M
options of sports for this event. These sports are numbered
1
through
M
.
Among these options, Takahashi will select one or more sports (possibly all) to be played in the event.
Takahashi knows that Person
i
's
j
-th favorite sport is Sport
A_{ij}
.
Each person will only participate in his/her most favorite sport among the ones that are actually played in the event, and will not participate in the other sports.
Takahashi is worried that one of the sports will attract too many people.
Therefore, he would like to carefully select sports to be played so that the number of the participants in the sport with the largest number of participants is minimized.
Find the minimum possible number of the participants in the sport with the largest number of participants.
Constraints
1 \leq N \leq 300
1 \leq M \leq 300
A_{i1}
,
A_{i2}
,
...
,
A_{iM}
is a permutation of the integers from
1
to
M
.
Input
Input is given from Standard Input in the following format:
N
M
A_{11}
A_{12}
...
A_{1M}
A_{21}
A_{22}
...
A_{2M}
:
A_{N1}
A_{N2}
...
A_{NM}
Output
Print the minimum possible number of the participants in the sport with the largest number of participants.
Sample Input 1
4 5
5 1 3 4 2
2 5 3 1 4
2 3 1 4 5
2 5 4 3 1
Sample Output 1
2
Assume that Sports
1
,
3
and
4
are selected to be played. In this case, Person
1
will participate in Sport
1
, Person
2
in Sport
3
, Person
3
in Sport
3
and Person
4
in Sport
4
.
Here, the sport with the largest number of participants is Sport
3
, with two participants.
There is no way to reduce the number of participants in the sport with the largest number of participants to
1
. Therefore, the answer is
2
.
Sample Input 2
3 3
2 1 3
2 1 3
2 1 3
Sample Output 2
3
Since all the people have the same taste in sports, there will be a sport with three participants, no matter what sports are selected.
Therefore, the answer is
3
.
Problem Description: Score : 800 points
Problem Statement
There are
X+Y+Z
people, conveniently numbered
1
through
X+Y+Z
.
Person
i
has
A_i
gold coins,
B_i
silver coins and
C_i
bronze coins.
Snuke is thinking of getting gold coins from
X
of those people, silver coins from
Y
of the people and bronze coins from
Z
of the people.
It is not possible to get two or more different colors of coins from a single person.
On the other hand, a person will give all of his/her coins of the color specified by Snuke.
Snuke would like to maximize the total number of coins of all colors he gets.
Find the maximum possible number of coins.
Constraints
1 \leq X
1 \leq Y
1 \leq Z
X+Y+Z \leq 10^5
1 \leq A_i \leq 10^9
1 \leq B_i \leq 10^9
1 \leq C_i \leq 10^9
Input
Input is given from Standard Input in the following format:
X
Y
Z
A_1
B_1
C_1
A_2
B_2
C_2
:
A_{X+Y+Z}
B_{X+Y+Z}
C_{X+Y+Z}
Output
Print the maximum possible total number of coins of all colors he gets.
Sample Input 1
1 2 1
2 4 4
3 2 1
7 6 7
5 2 3
Sample Output 1
18
Get silver coins from Person
1
, silver coins from Person
2
, bronze coins from Person
3
and gold coins from Person
4
.
In this case, the total number of coins will be
4+2+7+5=18
.
It is not possible to get
19
or more coins, and the answer is therefore
18
.
Sample Input 2
3 3 2
16 17 1
2 7 5
2 16 12
17 7 7
13 2 10
12 18 3
16 15 19
5 6 2
Sample Output 2
110
Sample Input 3
6 2 4
33189 87907 277349742
71616 46764 575306520
8801 53151 327161251
58589 4337 796697686
66854 17565 289910583
50598 35195 478112689
13919 88414 103962455
7953 69657 699253752
44255 98144 468443709
2332 42580 752437097
39752 19060 845062869
60126 74101 382963164
Sample Output 3
3093929975
Problem Description: Score : 100 points
Problem Statement
Snuke is giving cookies to his three goats.
He has two cookie tins. One contains
A
cookies, and the other contains
B
cookies. He can thus give
A
cookies,
B
cookies or
A+B
cookies to his goats (he cannot open the tins).
Your task is to determine whether Snuke can give cookies to his three goats so that each of them can have the same number of cookies.
Constraints
1 \leq A,B \leq 100
Both
A
and
B
are integers.
Input
Input is given from Standard Input in the following format:
A
B
Output
If it is possible to give cookies so that each of the three goats can have the same number of cookies, print
Possible
; otherwise, print
Impossible
.
Sample Input 1
4 5
Sample Output 1
Possible
If Snuke gives nine cookies, each of the three goats can have three cookies.
Sample Input 2
1 1
Sample Output 2
Impossible
Since there are only two cookies, the three goats cannot have the same number of cookies no matter what Snuke gives to them.
Problem Description: Score : 200 points
Problem Statement
Snuke has
N
sticks.
The length of the
i
-th stick is
l_i
.
Snuke is making a snake toy by joining
K
of the sticks together.
The length of the toy is represented by the sum of the individual sticks that compose it.
Find the maximum possible length of the toy.
Constraints
1 \leq K \leq N \leq 50
1 \leq l_i \leq 50
l_i
is an integer.
Input
Input is given from Standard Input in the following format:
N
K
l_1
l_2
l_3
...
l_{N}
Output
Print the answer.
Sample Input 1
5 3
1 2 3 4 5
Sample Output 1
12
You can make a toy of length
12
by joining the sticks of lengths
3
,
4
and
5
, which is the maximum possible length.
Sample Input 2
15 14
50 26 27 21 41 7 42 35 7 5 5 36 39 1 45
Sample Output 2
386
Problem Description: Score : 300 points
Problem Statement
Snuke and Raccoon have a heap of
N
cards. The
i
-th card from the top has the integer
a_i
written on it.
They will share these cards.
First, Snuke will take some number of cards from the top of the heap, then Raccoon will take all the remaining cards.
Here, both Snuke and Raccoon have to take at least one card.
Let the sum of the integers on Snuke's cards and Raccoon's cards be
x
and
y
, respectively.
They would like to minimize
|x-y|
.
Find the minimum possible value of
|x-y|
.
Constraints
2 \leq N \leq 2 \times 10^5
-10^{9} \leq a_i \leq 10^{9}
a_i
is an integer.
Input
Input is given from Standard Input in the following format:
N
a_1
a_2
...
a_{N}
Output
Print the answer.
Sample Input 1
6
1 2 3 4 5 6
Sample Output 1
1
If Snuke takes four cards from the top, and Raccoon takes the remaining two cards,
x=10
,
y=11
, and thus
|x-y|=1
. This is the minimum possible value.
Sample Input 2
2
10 -10
Sample Output 2
20
Snuke can only take one card from the top, and Raccoon can only take the remaining one card. In this case,
x=10
,
y=-10
, and thus
|x-y|=20
.
Problem Description: Score : 400 points
Problem Statement
Fennec and Snuke are playing a board game.
On the board, there are
N
cells numbered
1
through
N
, and
N-1
roads, each connecting two cells. Cell
a_i
is adjacent to Cell
b_i
through the
i
-th road. Every cell can be reached from every other cell by repeatedly traveling to an adjacent cell. In terms of graph theory, the graph formed by the cells and the roads is a tree.
Initially, Cell
1
is painted black, and Cell
N
is painted white. The other cells are not yet colored.
Fennec (who goes first) and Snuke (who goes second) alternately paint an uncolored cell.
More specifically, each player performs the following action in her/his turn:
Fennec: selects an uncolored cell that is adjacent to a
black
cell, and paints it
black
.
Snuke: selects an uncolored cell that is adjacent to a
white
cell, and paints it
white
.
A player loses when she/he cannot paint a cell. Determine the winner of the game when Fennec and Snuke play optimally.
Constraints
2 \leq N \leq 10^5
1 \leq a_i, b_i \leq N
The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N
a_1
b_1
:
a_{N-1}
b_{N-1}
Output
If Fennec wins, print
Fennec
; if Snuke wins, print
Snuke
.
Sample Input 1
7
3 6
1 2
3 1
7 4
5 7
1 4
Sample Output 1
Fennec
For example, if Fennec first paints Cell
2
black, she will win regardless of Snuke's moves.
Sample Input 2
4
1 4
4 2
2 3
Sample Output 2
Snuke
Problem Description: Score : 200 points
Problem Statement
There are
N
bags of biscuits. The
i
-th bag contains
A_i
biscuits.
Takaki will select some of these bags and eat all of the biscuits inside.
Here, it is also possible to select all or none of the bags.
He would like to select bags so that the total number of biscuits inside is congruent to
P
modulo
2
.
How many such ways to select bags there are?
Constraints
1 \leq N \leq 50
P = 0
or
1
1 \leq A_i \leq 100
Input
Input is given from Standard Input in the following format:
N
P
A_1
A_2
...
A_N
Output
Print the number of ways to select bags so that the total number of biscuits inside is congruent to
P
modulo
2
.
Sample Input 1
2 0
1 3
Sample Output 1
2
There are two ways to select bags so that the total number of biscuits inside is congruent to
0
modulo
2
:
Select neither bag. The total number of biscuits is
0
.
Select both bags. The total number of biscuits is
4
.
Sample Input 2
1 1
50
Sample Output 2
0
Sample Input 3
3 0
1 1 1
Sample Output 3
4
Two bags are distinguished even if they contain the same number of biscuits.
Sample Input 4
45 1
17 55 85 55 74 20 90 67 40 70 39 89 91 50 16 24 14 43 24 66 25 9 89 71 41 16 53 13 61 15 85 72 62 67 42 26 36 66 4 87 59 91 4 25 26
Sample Output 4
17592186044416
Problem Description: Score : 1000 points
Problem Statement
There are
N
balls in a row.
Initially, the
i
-th ball from the left has the integer
A_i
written on it.
When Snuke cast a spell, the following happens:
Let the current number of balls be
k
. All the balls with
k
written on them disappear at the same time.
Snuke's objective is to vanish all the balls by casting the spell some number of times.
This may not be possible as it is. If that is the case, he would like to modify the integers on the minimum number of balls to make his objective achievable.
By the way, the integers on these balls sometimes change by themselves.
There will be
M
such changes. In the
j
-th change, the integer on the
X_j
-th ball from the left will change into
Y_j
.
After each change, find the minimum number of modifications of integers on the balls Snuke needs to make if he wishes to achieve his objective before the next change occurs. We will assume that he is quick enough in modifying integers. Here, note that he does not actually perform those necessary modifications and leaves them as they are.
Constraints
1 \leq N \leq 200000
1 \leq M \leq 200000
1 \leq A_i \leq N
1 \leq X_j \leq N
1 \leq Y_j \leq N
Subscore
In the test set worth
500
points,
N \leq 200
and
M \leq 200
.
Input
Input is given from Standard Input in the following format:
N
M
A_1
A_2
...
A_N
X_1
Y_1
X_2
Y_2
:
X_M
Y_M
Output
Print
M
lines.
The
j
-th line should contain the minimum necessary number of modifications of integers on the balls to make Snuke's objective achievable.
Sample Input 1
5 3
1 1 3 4 5
1 2
2 5
5 4
Sample Output 1
0
1
1
After the first change, the integers on the balls become
2
,
1
,
3
,
4
,
5
, from left to right. Here, all the balls can be vanished by casting the spell five times. Thus, no modification is necessary.
After the second change, the integers on the balls become
2
,
5
,
3
,
4
,
5
, from left to right. In this case, at least one modification must be made. One optimal solution is to modify the integer on the fifth ball from the left to
2
, and cast the spell four times.
After the third change, the integers on the balls become
2
,
5
,
3
,
4
,
4
, from left to right. Also in this case, at least one modification must be made. One optimal solution is to modify the integer on the third ball from the left to
2
, and cast the spell three times.
Sample Input 2
4 4
4 4 4 4
4 1
3 1
1 1
2 1
Sample Output 2
0
1
2
3
Sample Input 3
10 10
8 7 2 9 10 6 6 5 5 4
8 1
6 3
6 2
7 10
9 7
9 9
2 4
8 1
1 8
7 7
Sample Output 3
1
0
1
2
2
3
3
3
3
2
Problem Description: Score : 1100 points
Problem Statement
There is a tree with
N
vertices numbered
1, 2, ..., N
.
The edges of the tree are denoted by
(x_i, y_i)
.
On this tree, Alice and Bob play a game against each other.
Starting from Alice, they alternately perform the following operation:
Select an existing edge and remove it from the tree, disconnecting it into two separate connected components. Then, remove the component that does not contain Vertex
1
.
A player loses the game when he/she is unable to perform the operation.
Determine the winner of the game assuming that both players play optimally.
Constraints
2 \leq N \leq 100000
1 \leq x_i, y_i \leq N
The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N
x_1
y_1
x_2
y_2
:
x_{N-1}
y_{N-1}
Output
Print
Alice
if Alice wins; print
Bob
if Bob wins.
Sample Input 1
5
1 2
2 3
2 4
4 5
Sample Output 1
Alice
If Alice first removes the edge connecting Vertices
1
and
2
, the tree becomes a single vertex tree containing only Vertex
1
.
Since there is no edge anymore, Bob cannot perform the operation and Alice wins.
Sample Input 2
5
1 2
2 3
1 4
4 5
Sample Output 2
Bob
Sample Input 3
6
1 2
2 4
5 1
6 3
3 2
Sample Output 3
Alice
Sample Input 4
7
1 2
3 7
4 6
2 3
2 4
1 5
Sample Output 4
Bob