There are attractions in Baku, numbered from
to
. There are also
two-way
roads, numbered from
to
. Each road connects two different attractions. It is
possible to travel between any pair of attractions through the roads.
Fatima is planning to visit all of the attractions in three days. She already decided that
she wants to visit attractions on the first day,
attractions on the second day, and
attractions on the third day. Therefore, she is going to partition the
attractions into
three sets
,
, and
of sizes
,
, and
, respectively. Each attraction will belong to
exactly one set, so
.
Fatima would like to find the sets ,
, and
, so that at least two out of the three
sets are connected. A set of attractions is called connected if it is possible to travel
between any pair of attractions in
by using the roads and without passing through
any attraction not in
. A partition of attractions into sets
,
, and
is called valid if
it satisfies the conditions described above.
Help Fatima find a valid partition of the attractions (given ,
, and
), or determine
that no valid partition exists. If there are multiple valid partitions, you may find any of
them.
Implementation details
You should implement the following procedure:
std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q)
: the number of attractions.
,
, and
: the desired sizes of sets
,
, and
.
and
: arrays of length
, containing the endpoints of the roads. For each
,
and
are the two attractions connected by road
.
- This procedure should return an array of length
. Denote the array by
. If there is no valid partition,
should contain
zeros. Otherwise, for
,
should be one of
,
, or
to denote that attraction
is assigned to set
,
, or
, respectively.
Examples
Example 1
Consider the following call:
find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5}, {1, 2, 3, 4, 6, 8, 7, 7, 5, 6})
A possible correct solution is . This solution describes the following
partition:
,
, and
. The sets
and
are
connected.
Example 2
Consider the following call:
find_split(6, 2, 2, 2, {0, 0, 0, 0, 0}, {1, 2, 3, 4, 5})
No valid partition exists. Therefore, the only correct answer is .
Constraints
- There is at most one road between each pair of attractions.
- It is possible to travel between any pair of attractions through the roads.
and
for
Subtasks
- (
points) Each attraction is an endpoint of at most two roads.
- (
points)
- (
points)
- (
points)
,
- (
points) No additional constraints.
Sample grader
The sample grader reads the input in the following format:
- line
:
- line
:
- line
(for
):
The sample grader prints a single line containing the array returned by find_split
.
Comments