CodeEff/ECCO huggingface dataset:
Problem Description: Score : 300 points
Problem Statement
You are given an integer
N
.
For two positive integers
A
and
B
, we will define
F(A,B)
as the larger of the following: the number of digits in the decimal notation of
A
, and the number of digits in the decimal notation of
B
.
For example,
F(3,11) = 2
since
3
has one digit and
11
has two digits.
Find the minimum value of
F(A,B)
as
(A,B)
ranges over all pairs of positive integers such that
N = A \times B
.
Constraints
1 \leq N \leq 10^{10}
N
is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print the minimum value of
F(A,B)
as
(A,B)
ranges over all pairs of positive integers such that
N = A \times B
.
Sample Input 1
10000
Sample Output 1
3
F(A,B)
has a minimum value of
3
at
(A,B)=(100,100)
.
Sample Input 2
1000003
Sample Output 2
7
There are two pairs
(A,B)
that satisfy the condition:
(1,1000003)
and
(1000003,1)
. For these pairs,
F(1,1000003)=F(1000003,1)=7
.
Sample Input 3
9876543210
Sample Output 3
6
Problem Description: Score : 200 points
Problem Statement
There is a kangaroo at coordinate
0
on an infinite number line that runs from left to right, at time
0
.
During the period between time
i-1
and time
i
, the kangaroo can either stay at his position, or perform a jump of length exactly
i
to the left or to the right.
That is, if his coordinate at time
i-1
is
x
, he can be at coordinate
x-i
,
x
or
x+i
at time
i
.
The kangaroo's nest is at coordinate
X
, and he wants to travel to coordinate
X
as fast as possible.
Find the earliest possible time to reach coordinate
X
.
Constraints
X
is an integer.
1≤X≤10^9
Input
The input is given from Standard Input in the following format:
X
Output
Print the earliest possible time for the kangaroo to reach coordinate
X
.
Sample Input 1
6
Sample Output 1
3
The kangaroo can reach his nest at time
3
by jumping to the right three times, which is the earliest possible time.
Sample Input 2
2
Sample Output 2
2
He can reach his nest at time
2
by staying at his position during the first second, and jumping to the right at the next second.
Sample Input 3
11
Sample Output 3
5
Problem Description: Score : 600 points
Problem Statement
AtCoDeer the deer has
N
cards with positive integers written on them. The number on the
i
-th card
(1≤i≤N)
is
a_i
.
Because he loves big numbers, he calls a subset of the cards
good
when the sum of the numbers written on the cards in the subset, is
K
or greater.
Then, for each card
i
, he judges whether it is
unnecessary
or not, as follows:
If, for any good subset of the cards containing card
i
, the set that can be obtained by eliminating card
i
from the subset is also good, card
i
is unnecessary.
Otherwise, card
i
is NOT unnecessary.
Find the number of the unnecessary cards. Here, he judges each card independently, and he does not throw away cards that turn out to be unnecessary.
Constraints
All input values are integers.
1≤N≤5000
1≤K≤5000
1≤a_i≤10^9 (1≤i≤N)
Partial Score
300
points will be awarded for passing the test set satisfying
N,K≤400
.
Input
The input is given from Standard Input in the following format:
N
K
a_1
a_2
...
a_N
Output
Print the number of the unnecessary cards.
Sample Input 1
3 6
1 4 3
Sample Output 1
1
There are two good sets: {
2,3
} and {
1,2,3
}.
Card
1
is only contained in {
1,2,3
}, and this set without card
1
, {
2,3
}, is also good. Thus, card
1
is unnecessary.
For card
2
, a good set {
2,3
} without card
2
, {
3
}, is not good. Thus, card
2
is NOT unnecessary.
Neither is card
3
for a similar reason, hence the answer is
1
.
Sample Input 2
5 400
3 1 4 1 5
Sample Output 2
5
In this case, there is no good set. Therefore, all the cards are unnecessary.
Sample Input 3
6 20
10 4 3 10 25 2
Sample Output 3
3
Problem Description: Score : 300 points
Problem Statement
Every day,
N
passengers arrive at Takahashi Airport.
The
i
-th passenger arrives at time
T_i
.
Every passenger arrived at Takahashi airport travels to the city by bus. Each bus can accommodate up to
C
passengers.
Naturally, a passenger cannot take a bus that departs earlier than the airplane arrives at the airport.
Also, a passenger will get angry if he/she is still unable to take a bus
K
units of time after the arrival of the airplane.
For that reason, it is necessary to arrange buses so that the
i
-th passenger can take a bus departing at time between
T_i
and
T_i + K
(inclusive).
When setting the departure times for buses under this condition, find the minimum required number of buses.
Here, the departure time for each bus does not need to be an integer, and there may be multiple buses that depart at the same time.
Constraints
2 \leq N \leq 100000
1 \leq C \leq 10^9
1 \leq K \leq 10^9
1 \leq T_i \leq 10^9
C
,
K
and
T_i
are integers.
Input
The input is given from Standard Input in the following format:
N
C
K
T_1
T_2
:
T_N
Output
Print the minimum required number of buses.
Sample Input 1
5 3 5
1
2
3
6
12
Sample Output 1
3
For example, the following three buses are enough:
A bus departing at time
4.5
, that carries the passengers arriving at time
2
and
3
.
A bus departing at time
6
, that carries the passengers arriving at time
1
and
6
.
A bus departing at time
12
, that carries the passenger arriving at time
12
.
Sample Input 2
6 3 3
7
6
2
8
10
6
Sample Output 2
3
Problem Description: Score : 800 points
Problem Statement
Takahashi has received an undirected graph with
N
vertices, numbered
1
,
2
, ...,
N
.
The edges in this graph are represented by
(u_i, v_i)
.
There are no self-loops and multiple edges in this graph.
Based on this graph, Takahashi is now constructing a new graph with
N^2
vertices, where each vertex is labeled with a pair of integers
(a, b)
(
1 \leq a \leq N
,
1 \leq b \leq N
).
The edges in this new graph are generated by the following rule:
Span an edge between vertices
(a, b)
and
(a', b')
if and only if both of the following two edges exist in the original graph: an edge between vertices
a
and
a'
, and an edge between vertices
b
and
b'
.
How many connected components are there in this new graph?
Constraints
2 \leq N \leq 100,000
0 \leq M \leq 200,000
1 \leq u_i < v_i \leq N
There exists no pair of distinct integers
i
and
j
such that
u_i = u_j
and
v_i = v_j
.
Input
The input is given from Standard Input in the following format:
N
M
u_1
v_1
u_2
v_2
:
u_M
v_M
Output
Print the number of the connected components in the graph constructed by Takahashi.
Sample Input 1
3 1
1 2
Sample Output 1
7
The graph constructed by Takahashi is as follows.
Sample Input 2
7 5
1 2
3 4
3 5
4 5
2 6
Sample Output 2
18
Problem Description: Score : 900 points
Problem Statement
You are developing frog-shaped robots, and decided to race them against each other.
First, you placed
N
robots onto a number line.
These robots are numbered
1
through
N
.
The current coordinate of robot
i
is
x_i
.
Here, all
x_i
are integers, and
0 < x_1 < x_2 < ... < x_N
.
You will repeatedly perform the following operation:
Select a robot on the number line. Let the coordinate of the robot be
x
. Select the destination coordinate, either
x-1
or
x-2
, that is not occupied by another robot. The robot now jumps to the selected coordinate.
When the coordinate of a robot becomes
0
or less, the robot is considered finished and will be removed from the number line immediately.
You will repeat the operation until all the robots finish the race.
Depending on your choice in the operation, the
N
robots can finish the race in different orders.
In how many different orders can the
N
robots finish the race?
Find the answer modulo
10^9+7
.
Constraints
2 ≤ N ≤ 10^5
x_i
is an integer.
0 < x_1 < x_2 < ... < x_N ≤ 10^9
Partial Score
In a test set worth
500
points,
N ≤ 8
.
Input
The input is given from Standard Input in the following format:
N
x_1
x_2
...
x_N
Output
Print the number of the different orders in which the
N
robots can finish the race, modulo
10^9+7
.
Sample Input 1
3
1 2 3
Sample Output 1
4
There are four different orders in which the three robots can finish the race:
(
Robot
1 →
Robot
2 →
Robot
3)
(
Robot
1 →
Robot
3 →
Robot
2)
(
Robot
2 →
Robot
1 →
Robot
3)
(
Robot
2 →
Robot
3 →
Robot
1)
Sample Input 2
3
2 3 4
Sample Output 2
6
There are six different orders in which the three robots can finish the race:
(
Robot
1 →
Robot
2 →
Robot
3)
(
Robot
1 →
Robot
3 →
Robot
2)
(
Robot
2 →
Robot
1 →
Robot
3)
(
Robot
2 →
Robot
3 →
Robot
1)
(
Robot
3 →
Robot
1 →
Robot
2)
(
Robot
3 →
Robot
2 →
Robot
1)
For example, the order
(
Robot
3 →
Robot
2 →
Robot
1)
can be achieved as shown in the figure below:
Sample Input 3
8
1 2 3 5 7 11 13 17
Sample Output 3
10080
Sample Input 4
13
4 6 8 9 10 12 14 15 16 18 20 21 22
Sample Output 4
311014372
Remember to print the answer modulo
10^9+7
.
This case is not included in the test set for the partial score.
Problem Description: Score : 100 points
Problem Statement
Snuke has a favorite restaurant.
The price of any meal served at the restaurant is
800
yen (the currency of Japan), and each time a customer orders
15
meals, the restaurant pays
200
yen back to the customer.
So far, Snuke has ordered
N
meals at the restaurant.
Let the amount of money Snuke has paid to the restaurant be
x
yen, and let the amount of money the restaurant has paid back to Snuke be
y
yen.
Find
x-y
.
Constraints
1 ≤ N ≤ 100
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
20
Sample Output 1
15800
So far, Snuke has paid
16000
yen, and the restaurant has paid back
200
yen. Thus, the answer is
15800
.
Sample Input 2
60
Sample Output 2
47200
Snuke has paid
48000
yen for
60
meals, and the restaurant has paid back
800
yen.
Problem Description: Score : 200 points
Problem Statement
Snuke loves working out. He is now exercising
N
times.
Before he starts exercising, his
power
is
1
. After he exercises for the
i
-th time, his power gets multiplied by
i
.
Find Snuke's power after he exercises
N
times. Since the answer can be extremely large, print the answer modulo
10^{9}+7
.
Constraints
1 ≤ N ≤ 10^{5}
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer modulo
10^{9}+7
.
Sample Input 1
3
Sample Output 1
6
After Snuke exercises for the first time, his power gets multiplied by
1
and becomes
1
.
After Snuke exercises for the second time, his power gets multiplied by
2
and becomes
2
.
After Snuke exercises for the third time, his power gets multiplied by
3
and becomes
6
.
Sample Input 2
10
Sample Output 2
3628800
Sample Input 3
100000
Sample Output 3
457992974
Print the answer modulo
10^{9}+7
.
Problem Description: Score : 300 points
Problem Statement
Snuke loves puzzles.
Today, he is working on a puzzle using
S
- and
c
-shaped pieces.
In this puzzle, you can combine two
c
-shaped pieces into one
S
-shaped piece, as shown in the figure below:
Snuke decided to create as many
Scc
groups as possible by putting together one
S
-shaped piece and two
c
-shaped pieces.
Find the maximum number of
Scc
groups that can be created when Snuke has
N
S
-shaped pieces and
M
c
-shaped pieces.
Constraints
1 ≤ N,M ≤ 10^{12}
Input
The input is given from Standard Input in the following format:
N
M
Output
Print the answer.
Sample Input 1
1 6
Sample Output 1
2
Two
Scc
groups can be created as follows:
Combine two
c
-shaped pieces into one
S
-shaped piece
Create two
Scc
groups, each from one
S
-shaped piece and two
c
-shaped pieces
Sample Input 2
12345 678901
Sample Output 2
175897
Problem Description: Score : 500 points
Problem Statement
Snuke, who loves animals, built a zoo.
There are
N
animals in this zoo. They are conveniently numbered
1
through
N
, and arranged in a circle.
The animal numbered
i (2≤i≤N-1)
is adjacent to the animals numbered
i-1
and
i+1
. Also, the animal numbered
1
is adjacent to the animals numbered
2
and
N
, and the animal numbered
N
is adjacent to the animals numbered
N-1
and
1
.
There are two kinds of animals in this zoo: honest sheep that only speak the truth, and lying wolves that only tell lies.
Snuke cannot tell the difference between these two species, and asked each animal the following question: "Are your neighbors of the same species?" The animal numbered
i
answered
s_i
. Here, if
s_i
is
o
, the animal said that the two neighboring animals are of the same species, and if
s_i
is
x
, the animal said that the two neighboring animals are of different species.
More formally, a sheep answered
o
if the two neighboring animals are both sheep or both wolves, and answered
x
otherwise.
Similarly, a wolf answered
x
if the two neighboring animals are both sheep or both wolves, and answered
o
otherwise.
Snuke is wondering whether there is a valid assignment of species to the animals that is consistent with these responses. If there is such an assignment, show one such assignment. Otherwise, print
-1
.
Constraints
3 ≤ N ≤ 10^{5}
s
is a string of length
N
consisting of
o
and
x
.
Input
The input is given from Standard Input in the following format:
N
s
Output
If there does not exist an valid assignment that is consistent with
s
, print
-1
.
Otherwise, print an string
t
in the following format. The output is considered correct if the assignment described by
t
is consistent with
s
.
t
is a string of length
N
consisting of
S
and
W
.
If
t_i
is
S
, it indicates that the animal numbered
i
is a sheep. If
t_i
is
W
, it indicates that the animal numbered
i
is a wolf.
Sample Input 1
6
ooxoox
Sample Output 1
SSSWWS
For example, if the animals numbered
1
,
2
,
3
,
4
,
5
and
6
are respectively a sheep, sheep, sheep, wolf, wolf, and sheep, it is consistent with their responses. Besides, there is another valid assignment of species: a wolf, sheep, wolf, sheep, wolf and wolf.
Let us remind you: if the neiboring animals are of the same species, a sheep answers
o
and a wolf answers
x
. If the neiboring animals are of different species, a sheep answers
x
and a wolf answers
o
.
Sample Input 2
3
oox
Sample Output 2
-1
Print
-1
if there is no valid assignment of species.
Sample Input 3
10
oxooxoxoox
Sample Output 3
SSWWSSSWWS
Problem Description: Score : 700 points
Problem Statement
Snuke loves constructing integer sequences.
There are
N
piles of stones, numbered
1
through
N
.
The pile numbered
i
consists of
a_i
stones.
Snuke will construct an integer sequence
s
of length
Σa_i
, as follows:
Among the piles with the largest number of stones remaining, let
x
be the index of the pile with the smallest index. Append
x
to the end of
s
.
Select a pile with one or more stones remaining, and remove a stone from that pile.
If there is a pile with one or more stones remaining, go back to step 1. Otherwise, terminate the process.
We are interested in the lexicographically smallest sequence that can be constructed. For each of the integers
1,2,3,...,N
, how many times does it occur in the lexicographically smallest sequence?
Constraints
1 ≤ N ≤ 10^{5}
1 ≤ a_i ≤ 10^{9}
Input
The input is given from Standard Input in the following format:
N
a_1
a_2
...
a_{N}
Output
Print
N
lines. The
i
-th line should contain the number of the occurrences of the integer
i
in the lexicographically smallest sequence that can be constructed.
Sample Input 1
2
1 2
Sample Output 1
2
1
The lexicographically smallest sequence is constructed as follows:
Since the pile with the largest number of stones remaining is pile
2
, append
2
to the end of
s
. Then, remove a stone from pile
2
.
Since the piles with the largest number of stones remaining are pile
1
and
2
, append
1
to the end of
s
(we take the smallest index). Then, remove a stone from pile
2
.
Since the pile with the largest number of stones remaining is pile
1
, append
1
to the end of
s
. Then, remove a stone from pile
1
.
The resulting sequence is
(2,1,1)
. In this sequence,
1
occurs twice, and
2
occurs once.
Sample Input 2
10
1 2 1 3 2 4 2 5 8 1
Sample Output 2
10
7
0
4
0
3
0
2
3
0
Problem Description: Score : 100 points
Problem Statement
Alice and Bob are playing
One Card Poker
.
One Card Poker is a two-player game using playing cards.
Each card in this game shows an integer between
1
and
13
, inclusive.
The
strength
of a card is determined by the number written on it, as follows:
Weak
2
<
3
<
4
<
5
<
6
<
7
<
8
<
9
<
10
<
11
<
12
<
13
<
1
Strong
One Card Poker is played as follows:
Each player picks one card from the deck. The chosen card becomes the player's hand.
The players reveal their hands to each other. The player with the stronger card wins the game.
If their cards are equally strong, the game is drawn.
You are watching Alice and Bob playing the game, and can see their hands.
The number written on Alice's card is
A
, and the number written on Bob's card is
B
.
Write a program to determine the outcome of the game.
Constraints
1≦A≦13
1≦B≦13
A
and
B
are integers.
Input
The input is given from Standard Input in the following format:
A
B
Output
Print
Alice
if Alice will win. Print
Bob
if Bob will win. Print
Draw
if the game will be drawn.
Sample Input 1
8 6
Sample Output 1
Alice
8
is written on Alice's card, and
6
is written on Bob's card.
Alice has the stronger card, and thus the output should be
Alice
.
Sample Input 2
1 1
Sample Output 2
Draw
Since their cards have the same number, the game will be drawn.
Sample Input 3
13 1
Sample Output 3
Bob
Problem Description: Score : 300 points
Problem Statement
You are given an undirected unweighted graph with
N
vertices and
M
edges that contains neither self-loops nor double edges.
Here, a
self-loop
is an edge where
a_i = b_i (1≤i≤M)
, and
double edges
are two edges where
(a_i,b_i)=(a_j,b_j)
or
(a_i,b_i)=(b_j,a_j) (1≤i<j≤M)
.
How many different paths start from vertex
1
and visit all the vertices exactly once?
Here, the endpoints of a path are considered visited.
For example, let us assume that the following undirected graph shown in Figure 1 is given.
Figure 1: an example of an undirected graph
The following path shown in Figure 2 satisfies the condition.
Figure 2: an example of a path that satisfies the condition
However, the following path shown in Figure 3 does not satisfy the condition, because it does not visit all the vertices.
Figure 3: an example of a path that does not satisfy the condition
Neither the following path shown in Figure 4, because it does not start from vertex
1
.
Figure 4: another example of a path that does not satisfy the condition
Constraints
2≦N≦8
0≦M≦N(N-1)/2
1≦a_i<b_i≦N
The given graph contains neither self-loops nor double edges.
Input
The 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
Print the number of the different paths that start from vertex
1
and visit all the vertices exactly once.
Sample Input 1
3 3
1 2
1 3
2 3
Sample Output 1
2
The given graph is shown in the following figure:
The following two paths satisfy the condition:
Sample Input 2
7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7
Sample Output 2
1
This test case is the same as the one described in the problem statement.
Problem Description: Score : 400 points
Problem Statement
Dolphin is planning to generate a small amount of a certain chemical substance C.
In order to generate the substance C, he must prepare a solution which is a mixture of two substances A and B in the ratio of
M_a:M_b
.
He does not have any stock of chemicals, however, so he will purchase some chemicals at a local pharmacy.
The pharmacy sells
N
kinds of chemicals. For each kind of chemical, there is exactly one package of that chemical in stock.
The package of chemical
i
contains
a_i
grams of the substance A and
b_i
grams of the substance B, and is sold for
c_i
yen (the currency of Japan).
Dolphin will purchase some of these packages. For some reason, he must use all contents of the purchased packages to generate the substance C.
Find the minimum amount of money required to generate the substance C.
If it is not possible to generate the substance C by purchasing any combination of packages at the pharmacy, report that fact.
Constraints
1≦N≦40
1≦a_i,b_i≦10
1≦c_i≦100
1≦M_a,M_b≦10
gcd(M_a,M_b)=1
a_i
,
b_i
,
c_i
,
M_a
and
M_b
are integers.
Input
The input is given from Standard Input in the following format:
N
M_a
M_b
a_1
b_1
c_1
a_2
b_2
c_2
:
a_N
b_N
c_N
Output
Print the minimum amount of money required to generate the substance C. If it is not possible to generate the substance C, print
-1
instead.
Sample Input 1
3 1 1
1 2 1
2 1 2
3 3 10
Sample Output 1
3
The amount of money spent will be minimized by purchasing the packages of chemicals
1
and
2
.
In this case, the mixture of the purchased chemicals will contain
3
grams of the substance A and
3
grams of the substance B, which are in the desired ratio:
3:3=1:1
.
The total price of these packages is
3
yen.
Sample Input 2
1 1 10
10 10 10
Sample Output 2
-1
The ratio
1:10
of the two substances A and B cannot be satisfied by purchasing any combination of the packages. Thus, the output should be
-1
.
Problem Description: Score : 300 points
Problem Statement
There are
N
integers written on a blackboard. The
i
-th integer is
A_i
.
Takahashi will repeatedly perform the following operation on these numbers:
Select a pair of integers,
A_i
and
A_j
, that have the same parity (that is, both are even or both are odd) and erase them.
Then, write a new integer on the blackboard that is equal to the sum of those integers,
A_i+A_j
.
Determine whether it is possible to have only one integer on the blackboard.
Constraints
2 ≦ N ≦ 10^5
1 ≦ A_i ≦ 10^9
A_i
is an integer.
Input
The input is given from Standard Input in the following format:
N
A_1
A_2
…
A_N
Output
If it is possible to have only one integer on the blackboard, print
YES
. Otherwise, print
NO
.
Sample Input 1
3
1 2 3
Sample Output 1
YES
It is possible to have only one integer on the blackboard, as follows:
Erase
1
and
3
from the blackboard, then write
4
. Now, there are two integers on the blackboard:
2
and
4
.
Erase
2
and
4
from the blackboard, then write
6
. Now, there is only one integer on the blackboard:
6
.
Sample Input 2
5
1 2 3 4 5
Sample Output 2
NO
Problem Description: Score : 500 points
Problem Statement
There are
N
boxes arranged in a circle. The
i
-th box contains
A_i
stones.
Determine whether it is possible to remove all the stones from the boxes by repeatedly performing the following operation:
Select one box. Let the box be the
i
-th box. Then, for each
j
from
1
through
N
, remove exactly
j
stones from the
(i+j)
-th box. Here, the
(N+k)
-th box is identified with the
k
-th box.
Note that the operation cannot be performed if there is a box that does not contain enough number of stones to be removed.
Constraints
1 ≦ N ≦ 10^5
1 ≦ A_i ≦ 10^9
Input
The input is given from Standard Input in the following format:
N
A_1
A_2
…
A_N
Output
If it is possible to remove all the stones from the boxes, print
YES
. Otherwise, print
NO
.
Sample Input 1
5
4 5 1 2 3
Sample Output 1
YES
All the stones can be removed in one operation by selecting the second box.
Sample Input 2
5
6 9 12 10 8
Sample Output 2
YES
Sample Input 3
4
1 2 3 1
Sample Output 3
NO
Problem Description: Score : 700 points
Problem Statement
There is a tree with
N
vertices, numbered
1
through
N
.
The
i
-th of the
N-1
edges connects vertices
a_i
and
b_i
.
Currently, there are
A_i
stones placed on vertex
i
.
Determine whether it is possible to remove all the stones from the vertices by repeatedly performing the following operation:
Select a pair of different leaves. Then, remove exactly one stone from every vertex on the path between those two vertices.
  Here, a
leaf
is a vertex of the tree whose degree is
1
, and the selected leaves themselves are also considered as vertices on the path connecting them.
Note that the operation cannot be performed if there is a vertex with no stone on the path.
Constraints
2 ≦ N ≦ 10^5
1 ≦ a_i,b_i ≦ N
0 ≦ A_i ≦ 10^9
The given graph is a tree.
Input
The input is given from Standard Input in the following format:
N
A_1
A_2
…
A_N
a_1
b_1
:
a_{N-1}
b_{N-1}
Output
If it is possible to remove all the stones from the vertices, print
YES
. Otherwise, print
NO
.
Sample Input 1
5
1 2 1 1 2
2 4
5 2
3 2
1 3
Sample Output 1
YES
All the stones can be removed, as follows:
Select vertices
4
and
5
. Then, there is one stone remaining on each vertex except
4
.
Select vertices
1
and
5
. Then, there is no stone on any vertex.
Sample Input 2
3
1 2 1
1 2
2 3
Sample Output 2
NO
Sample Input 3
6
3 2 2 2 2 2
1 2
2 3
1 4
1 5
4 6
Sample Output 3
YES