2024-2025 ICPC NERC, Kyrgyzstan Regional Contest
A. New Functionality
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, a new feature has been added to the main Kyrgyz website for programming competitions — the division of problems into separate volumes.

Volumes are numbered with integers starting from 1. Inside each volume, problems are numbered with integers from 0 to n.

Thus, each problem corresponds to a pair of numbers (v, k) — the volume number and the number within the volume, respectively.

Additionally, within each problem, there is a button labeled "go to next":

  • If k < n, the button opens problem (v, k + 1).
  • Otherwise, the button opens problem (v + 1, 0).

At the moment, you are on the page of problem (a, b). You are interested in how many button presses are required to reach problem (c, d)?

Input

The first line contains an integer n (1 ≤ n ≤ 1000) — the maximum possible problem number within a volume.

The second line contains two integers a and b (1 ≤ a ≤ 1000, 0 ≤ b ≤ n) — the number of the problem you are currently on.

The third line contains two integers c and d (1 ≤ c ≤ 1000, 0 ≤ d ≤ n) — the number of the problem you want to reach.

It is guaranteed that it is possible to reach problem (c, d) from problem (a, b):

  • either a < c;
  • or a = c and b < d.
Output

In a single line, output an integer — the required number of presses of the "go to next" button after which you will reach problem (c, d) from problem (a, b).

Examples
Input
12
2 5
2 8
Output
3
Input
8
3 4
4 5
Output
10
Input
14
2 11
4 1
Output
20
Note

First test case

The sequence of presses (2, 5) — (2, 6) — (2, 7) — (2, 8) — a total of 3 presses.

Second test case

The sequence of presses:

  • (3, 4) — (3, 8) — a total of 4 presses;
  • (3, 8) — (4, 0) — 1 press;
  • (4, 0) — (4, 5) — another 5 presses.

A total of 10 presses.

B. Scientific Hypotheses
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Professor Termitov is studying $$$n$$$ new hypotheses in the scientific world.

It is known that the $$$i$$$-th hypothesis has an impossibility index $$$p_i$$$. The professor will believe in a hypothesis that is sufficiently plausible but will refuse to believe in one that seems completely fantastic.

Whether the professor believes in the $$$i$$$-th hypothesis depends on his level of imagination $$$f_{i - 1}$$$:

  • If $$$p_i \le f_{i - 1} + c$$$, then the professor believes in the hypothesis ($$$c$$$ is the trust credit parameter).

    In this case, his level of imagination will become $$$f_{i} = \max{(f_{i - 1}, p_i)}$$$.

  • If $$$p_i \gt f_{i - 1} + c$$$, then the professor does not believe in the hypothesis.

    In this case, his level of imagination will become $$$f_{i} = f_{i - 1} - \max{(d, p_i - f_{i - 1} - c)}$$$, where $$$d$$$ is the disappointment degree parameter.

It is also known that none of the values $$$f_0 \dots f_n$$$ can be negative.

You happened to witness this process through a laboratory window. In the end, you saw all the reactions of your colleague $$$r_i$$$ (believed / did not believe), but you did not hear the hypotheses themselves.

Now you are interested in finding any set $$$p_i$$$ that leads to the given sequence of reactions $$$r_i$$$ (considering the constraints on $$$f_i$$$).

If there are multiple suitable sets, output any set with the minimally possible $$$\max{(p_i)}$$$.

Input

The first line contains integers $$$n$$$, $$$f_0$$$, $$$c$$$, $$$d$$$ $$$(1 \le n \le 3 \cdot 10^5, \, 1 \le f_0, \, c, \, d \le 5000)$$$ — the number of hypotheses, the initial value of the professor's level of imagination, and the parameters of trust credit and disappointment degree, respectively.

The second line contains a string $$$r$$$ $$$(|r| = n; r_i \in [T, F])$$$ — the professor's reactions to the $$$i$$$-th hypothesis.

If $$$r_i = T$$$, then the professor believed in the $$$i$$$-th hypothesis; if $$$r_i = F$$$, then the $$$i$$$-th hypothesis was deemed too implausible.

Output

In the first line, output YES if the sequence $$$p$$$ can be constructed, and NO if such a sequence does not exist.

If the sequence exists, output two more lines.

In the second line, output an integer $$$pmax$$$ — the maximum value among all values $$$p_i$$$.

In the third line, output $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ $$$(0 \le p_i \le pmax)$$$ — suitable values of the impossibility indices.

Examples
Input
5 3 2 1
TFFTT
Output
YES
6
1 6 5 2 0
Input
3 4 1 2
FFF
Output
NO
Note

First test example

Let's show how the given set $$$p_i$$$ leads to the specified set of reactions.

  • $$$p_1 \le f_0 + c$$$ ($$$1 \le 3 + 2$$$), so the professor believed in hypothesis $$$1$$$.

    His imagination remained equal to $$$f_1 = \max{(3, 1)} = 3$$$.

  • $$$p_2 \gt f_1 + c$$$ ($$$6 \gt 3 + 2$$$), so the professor did not believe in hypothesis $$$2$$$.

    His imagination became $$$f_2 = 3 - \max{(1, 6 - 3 - 2)} = 3 - 1 = 2$$$.

  • $$$p_3 \gt f_2 + c$$$ ($$$5 \gt 2 + 2$$$), so the professor did not believe in hypothesis $$$3$$$.

    His imagination became $$$f_3 = 2 - \max{(1, 5 - 2 - 2)} = 2 - 1 = 1$$$.

  • $$$p_4 \le f_3 + c$$$ ($$$2 \le 1 + 2$$$), so the professor believed in hypothesis $$$4$$$.

    His imagination became $$$f_4 = \max{(1, 2)} = 2$$$.

  • $$$p_5 \le f_4 + c$$$ ($$$0 \le 2 + 2$$$), so the professor believed in hypothesis $$$5$$$.

    His imagination became $$$f_5 = \max{(2, 0)} = 2$$$.

It can be shown that it is impossible to construct a set with $$$pmax \lt 6$$$ — this is the smallest value at which $$$r_2 = F$$$.

Also, note that the set provided in the answer is not the only possible one.

For example, the following sets are also among the possible answers to the problem:

  • $$$[3, 6, 5, 0, 2]$$$;
  • $$$[0, 6, 5, 3, 1]$$$;
  • etc.

Second test example

  • $$$r_1 = F$$$, which means $$$p_1 \gt f_0 + c$$$ ($$$p_1 \gt 4 + 1$$$).

    The $$$p_1$$$ that leads to the smallest decrease in imagination is $$$6$$$ or $$$7$$$.

    In this case, $$$f_1 = 4 - \max{(2, 6 - 4 - 1)} = 4 - 2 = 2$$$.

  • $$$r_2 = F$$$, which means $$$p_2 \gt f_1 + c$$$ ($$$p_2 \gt 2 + 1$$$).

    The $$$p_2$$$ that leads to the smallest decrease in imagination is $$$4$$$ or $$$5$$$.

    In this case, $$$f_2 = 2 - \max{(2, 5 - 2 - 1)} = 2 - 2 = 0$$$.

  • $$$r_3 = F$$$, which means $$$p_3 \gt f_2 + c$$$ ($$$p_3 \gt 0 + 1$$$).

    The $$$p_3$$$ that leads to the smallest decrease in imagination is $$$2$$$ or $$$3$$$.

    In this case, $$$f_3 = 0 - \max{(2, 2 - 0 - 1)} = 0 - 2 = -2$$$.

At each step, we tried to minimize the decrease in the level of imagination, but still ended up with a negative value.

This indicates that there is no set $$$p$$$ that leads to the given sequence of reactions.

C. Tomorrow Will Be Better Than Yesterday
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Pavel knows for sure — tomorrow is always better than yesterday.

He decided to prove this using geometry.

To do this, Pavel considered n consecutive days and assigned a point on the plane (xi, yi) to each day.

He considers day i + 1 to be better than day i if one of the two conditions is met:

  • either xi < xi + 1;
  • or xi = xi + 1, but yi < yi + 1.

Pavel is only unsure about one thing — whether he has chosen the correct coordinate system for his calculations. He is confident that only rotations and/or reflections can be used to find the correct coordinate system.

Help Pavel — find any rectangular (orthogonal) coordinate system in which each subsequent day will be better than the previous one.

Input

The first line contains an integer n (1 ≤ n ≤ 105) — the number of days analyzed by Pavel.

Each of the following n lines contains two integers xi and yi ( - 105 ≤ xi,  yi ≤ 105) — the point assigned by Pavel to the i-th day.

Output

In the first line, print YES if such a rectangular coordinate system exists, and NO otherwise.

If the desired coordinate system exists, print two more lines.

In the second line, print two integers Xx and Yx (|Xx|, |Yx| ≤ 109;|Xx| + |Yx| > 0) — the coordinates of the vector aligned with the axis Ox of the new coordinate system.

In the third line, print two integers Xy and Yy (|Xy|, |Yy| ≤ 109;|Xy| + |Yy| > 0) — the coordinates of the vector aligned with the axis Oy of the new coordinate system.

The vectors (Xx, Yx) and (Xy, Yy) must be perpendicular to each other.

If there are multiple valid answers, print any.

Examples
Input
9
3 3
2 3
3 2
1 3
2 2
3 1
1 2
2 1
1 1
Output
YES
-1 -1
1 -1
Input
4
1 1
1 2
2 2
2 1
Output
NO
Input
1
100000 100000
Output
YES
-100000 100000
-100000 -100000
Input
2
0 0
0 0
Output
NO
Note

First test example

First, consider the points assigned to the days and the found vectors in the original coordinate system:

Now let's show these same points in the coordinate system based on the found vectors:

The coordinates of the points after transitioning to the new coordinate system:

  1. (3, 3) — ( - 3, 0);
  2. (2, 3) — ( - 2.5,  - 0.5);
  3. (3, 2) — ( - 2.5, 0.5);
  4. (1, 3) — ( - 2,  - 1);
  5. (2, 2) — ( - 2, 0);
  6. (3, 1) — ( - 2, 1);
  7. (1, 2) — ( - 1.5,  - 0.5);
  8. (2, 1) — ( - 1.5, 0.5);
  9. (1, 1) — ( - 1, 0).

It is clear that each subsequent point is "better" than the previous one in the new coordinate system.

D. Conspiracy Theory
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A set of events is given by an array of integers ai.

You believe that from event number i, event number j could be anticipated if both of the following conditions are true:

  • ai < aj;
  • the greatest common divisor of ai and aj is different from 1.

A chain of events, where each subsequent event could be anticipated from the previous one, is called a conspiracy.

Prove to everyone that your conspiracy theory is not just a theory — find a conspiracy consisting of the largest number of events.

Input

The first line contains an integer n (1 ≤ n ≤ 106) — the number of events.

The second line contains n integers a1, a2, ..., an (1 ≤ aj ≤ 2·106) — the parameters of the events.

Output

In the first line, output an integer k (1 ≤ k ≤ n)  — the maximum possible size of the conspiracy.

In the second line, output k integers pj (1 ≤ pj ≤ n) separated by spaces  — the indices of these events in the order of anticipation.

In case there are multiple conspiracies of maximum size, output any of them.

Examples
Input
5
1 2 3 4 5
Output
2
2 4
Input
8
8 7 10 3 6 5 3 11
Output
4
4 5 1 3
Input
3
2 2 2
Output
1
1
Note

First test case

The sequence [2;4] is a conspiracy, as from the event a2 = 2 one can predict a4 = 4:

  • 2 < 4;
  • ( — greatest common divisor).

Second test case

The sequence [4;5, 1, 3] is a conspiracy, as:

  • a4 = 4;
  • a5 = 6: 3 < 6, ;
  • a1 = 8: 6 < 8, ;
  • a3 = 10: 8 < 10, .

Third test case

In this example, a conspiracy of any two events is impossible, as all ai are equal to each other.

At the same time, any event is formally a conspiracy by itself, so the size of the answer is always at least 1.

E. Training Camps
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Meder and Kylychbek are organizing training camps for the best competitive programmers in Kyrgyzstan.

They have already announced n study topics that the participants must familiarize themselves with during the process.

But there is a problem — it is necessary to create a schedule for the camps in such a way that both instructors are satisfied.

First, not all topics can be taught one after another. There are k connections between study topics (fi, si) such that topic si can be taught immediately after fi, and topic si is always strictly harder than topic fi.

Formally: it is guaranteed that if there is a connection (f, s), then there is no sequence of connections that allows teaching f after reading s.

Second, each instructor has their favorite topic that they prefer to teach on the first day of the camp.

Neither Meder nor Kylychbek will agree to start their part of the camp with any other topic.

It is also guaranteed that there are no connections allowing the favorite topics of the instructors to be taught after another topic.

Third, the final schedule must include each of the n announced topics at least once (but both instructors can teach the same topic if necessary).

Help Meder and Kylychbek — find a suitable sequence of study topics for each instructor so that all three of the above conditions are met.

Input

The first line contains two integers n and m (2 ≤ n ≤ 2·105,  1 ≤ m ≤ 2·105) — the number of topics planned for the camps, and the number of connections between topics.

The second line contains two integers tM and tK (1 ≤ tM, tK ≤ n,  tM ≠ tK) — the numbers of Meder's and Kylychbek's favorite topics, respectively.

Each of the following m lines contains two integers fi and si (1 ≤ fi, si ≤ n,  fi ≠ si;si ≠ tM;si ≠ tK) — the topics included in the i-th connection (topic si can be taught after reading fi).

It is guaranteed that if there is a connection (f, s), then there is no sequence of connections that allows teaching f after reading s.

Output

In the first line, print YES if Meder and Kylychbek can teach all n topics, and NO otherwise.

If the camps can be held, then print four more lines.

In the second line, print the integer dM — the number of topics that Meder will teach, starting with topic tM.

In the third line, print dM integers — the sequence of topics that Meder will teach, starting with topic tM.

In the fourth line, print the integer dK — the number of topics that Kylychbek will teach, starting with topic tK.

In the fifth line, print dK integers — the sequence of topics that Kylychbek will teach, starting with topic tK.

Examples
Input
6 7
1 2
1 3
1 4
2 3
2 4
3 5
4 5
3 6
Output
YES
3
1 3 6 
3
2 4 5
Input
6 6
1 3
1 2
2 4
3 4
3 5
5 6
4 6
Output
YES
4
1 2 4 6 
3
3 5 6
Input
6 5
1 2
1 3
2 3
3 4
3 5
3 6
Output
NO
Input
5 5
1 2
1 3
2 3
3 4
2 4
4 5
Output
YES
4
1 3 4 5 
4
2 3 4 5
Note

First test example

  • Meder started with his favorite topic 1, moved to topic 3, and finished his lectures on topic 6.
  • Kylychbek started with his favorite topic 2, moved to topic 4, and finished his lectures on topic 5.

In total, the instructors taught all n = 6 topics.

Second test example

Meder and Kylychbek both taught topic 6. A schedule where topic 6 is taught by only one of the two instructors would also be correct.

Third test example

Meder and Kylychbek will not be able to teach topics 4, 5, and 6 during the camp — only any two of them.

Fourth test example

Either Meder or Kylychbek could have taught only their favorite topic and stopped there — the other instructor would still teach all the remaining topics of the camp.

F. Volunteering
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Artem is organizing the Championship of Kyrgyzstan in programming.

The competition will take place in the time interval [S;F].

To assist in organizing the competition, Artem has recruited n volunteers. It is known that the i-th volunteer will be able to help in the time interval [bi, ei].

Artem understands that anything can happen, so for each moment t in time, he introduced the "help index" H(t) — the number of volunteers who can help him solve various problems at time t.

Formally, the help index H(t) is equal to the number of volunteers such that bi ≤ t ≤ ei.

Artem is considering various scenarios, so for each value h [1... n], he wants to know the total time during the championship when the help index H(t) will be strictly less than h.

Input

The first line contains an integer n (1 ≤ n ≤ 3·105) — the number of volunteers.

The second line contains integers S and F (1 ≤ S < F ≤ 109) — the start and end of the time interval of the championship.

Each of the next n lines contains two integers bi and ei (1 ≤ bi < ei ≤ 109) — the start and end of the time segment when the i-th volunteer is available.

Output

Output n numbers t1, t2, ..., tn, where th is the total time during the championship when the "help index" is strictly less than h.

Example
Input
5
10 20
5 12
16 19
15 25
8 14
13 17
Output
0 3 9 10 10
Note

First test example

  • The help index will never be 0 during the championship; hence t1 = 0.
  • The help index 1 will be in the intervals [12;13], [14;15], and [19;20] — the total duration of the intervals is 3; hence t2 = 3 + 0 = 3.
  • The help index 2 will be in the intervals [10;12], [13;14], [15;16], and [17;19] — the total duration is 6; hence t3 = 6 + 3 + 0 = 9.
  • The help index 3 will be in the interval [16;17] — the total duration is 1; hence t4 = 1 + 6 + 3 + 0 = 10.
  • The help index will never be equal to 4, so t5 = 10 similarly to t4.

G. Exhausting Training
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Aidar is preparing for another international olympiad.

In Aidar's opinion, the success of his performance depends on two indicators — the speed of coding and the speed of generating ideas.

Aidar knows that at the moment his coding speed is Sp, and his idea generation speed is Sm.

Every day, Aidar will spend Tp minutes training his coding speed, which will increase his coding speed by Dp every two days.

Similarly, every day Aidar will spend Tm minutes training his idea generation speed, which will increase his idea generation speed by Dm every two days.

Note that the transition from "quantity to quality" is not instantaneous, so after one day of training, Aidar will not feel an increase of .

Aidar can also conduct "intensive" training:

  • Aidar can train his coding speed for 4·Tp minutes instead of Tp — in this case, he will feel an increase in his coding skill by Dp after just one day.
  • Similarly, Aidar can train his idea generation speed for 4·Tm minutes instead of Tm — in this case, he will feel an increase in his idea generation skill by Dm after just one day.
  • Aidar can conduct "intensive" training for both indicators at the same time if he considers it necessary.

Aidar will consider himself sufficiently prepared if both speeds (coding and idea generation) are not lower than the value E.

Aidar wants to reach a sufficient level of preparedness as soon as possible (but at the same time does not want to expend excessive effort), so he asks you to determine:

  • the minimum number of days in which Aidar can achieve a sufficient level of preparedness;
  • the minimum total number of minutes he can spend on preparation (given the achievement of the minimum number of days).
Input

The first line contains integers Sp, Sm, Dp, Dm, Tp, Tm, E (1 ≤ Sp,  Sm,  E ≤ 108,   1 ≤ Dp,  Dm ≤ 105,   1 ≤ Tp,  Tm ≤ 108) — the initial values of Aidar's skills, the indicators of skill change, the required number of minutes for regular training, and the sufficient level of preparedness, respectively.

Output

In the first line, output an integer — the minimum number of days in which Aidar can achieve a sufficient level of preparedness.

In the second line, output an integer — the minimum total number of minutes he can spend on preparation (given the achievement of the minimum number of days).

Examples
Input
1 3 2 1 3 10 18
Output
15
672
Input
3 1 1 2 1000 1 3
Output
1
1004
Note

First test case

It is easy to notice that in the optimal solution Aidar will have to undergo intensive training for creativity every day.

In total, there will be days of intensive creativity training — a total of 15·4·10 = 600 minutes.

For typing practice, Aidar can apply the following resource distribution:

  • Spend 3 days on intensive training — this way he can increase his skill by 3·2 = 6, spending 3·4·3 = 36 minutes;
  • Spend the remaining 12 days on regular training — this way he will increase his skill by another , spending 12·3 = 36 minutes.

In total, Aidar will spend 600 + 72 = 672 minutes in this case.

Note that Aidar will not be able to complete his training in 15 days if he only does two intensive typing sessions:

  • In 2 days of intensive training, he will gain 2·2 = 4 skill points;
  • In the remaining 13 days of regular training, Aidar will increase his skill by another .

In total, he will have 1 + 4 + 12 = 17 skill points, which will not be enough for a sufficient level of readiness.

H. Tiring Wait
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Anatoly agreed with Slava to travel together to the new bus station.

The guys agreed to go together either from stop A or from the next stop B.

It is known that Slava has already boarded the necessary bus and is heading in the direction of "A B" (that is, he will first pass stop A and then stop B).

Anatoly arrived at stop B earlier than Slava but quickly realized that he misjudged the weather forecast — a heavy rain began with a piercing cold wind.

To avoid freezing, Anatoly decided to take the first bus that arrived and go to stop A to wait there. However, it didn't get any warmer at stop A, so Anatoly jumped on a bus heading to stop B...

Let's describe the process more formally:

  • If Anatoly is at stop B, he will go to stop A only if he can arrive there strictly earlier than the bus with Slava arrives.
  • If Anatoly is at stop A, he will go to stop B only if he can arrive there strictly earlier than the bus with Slava arrives at stop A.

It is known that all buses travel the distance between stops A and B (in both directions) in d minutes.

It is also known that if Anatoly gets off the bus at time t, he can board the next bus no earlier than t + 1 (he needs to cross the road, at least).

Knowing the arrival times of all buses at stop B, determine:

  • at which stop Anatoly will board the bus that Slava is on;
  • how many buses Anatoly will manage to ride before they meet.
Input

The first line contains space-separated integers n, m, d (1 ≤ n,  m ≤ 106,  1 ≤ d ≤ 106) — the number of buses going to stop B from stop A, the number of buses going to stop B from the opposite side, and the travel time between stops A and B, respectively.

The second line contains space-separated n integers a1, a2, ..., an (0 ≤ a1 < a2 < ... < an ≤ 106) — the moments in time when buses coming from stop A arrive at stop B.

Slava is on the last of these buses.

The third line contains m integers b1, b2, ..., bm (0 ≤ b1 < b2 < ... < bm ≤ 106) — the moments in time when buses coming from the opposite side arrive at stop B.

Output

In the first line, output a space-separated character and an integer:

  • the character A if Anatoly boards the bus with Slava at stop A, or the character B if Anatoly boards at stop B;
  • the number of buses Anatoly has ridden by that moment.
Example
Input
5 6 4
8 15 24 26 30
1 7 10 16 22 27
Output
A 3
Note

First test example

Slava will arrive at stop B at time 30, and at stop A respectively at 30 - 4 = 26.

  • At time 1, Anatoly will board the bus going from B to A.
  • At time 1 + 4 = 5, Anatoly will arrive at stop A.
  • At time 15 - 4 = 11, Anatoly will board the bus going from A to B.
  • At time 15, Anatoly will arrive at stop B.
  • At time 16, Anatoly will board the bus going from B to A.
  • At time 16 + 4 = 20, Anatoly will arrive at stop A.
  • Note that Anatoly will not be able to board the bus to stop B at time 24 - 4 = 20, as he needs at least one minute to transfer.
  • Also, note that Anatoly will not be able to board the bus to stop B at time 26 - 4 = 22, as in that case he would arrive at stop B at time 26 — Slava will already arrive at stop A at that moment.
  • Consequently, Anatoly will wait for Slava at stop A, having ridden on three buses.

I. Fair Diversity
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

When Anatoly and Slava arrived in Bishkek, they decided to explore its most interesting cafes and restaurants as soon as possible.

To do this, the guys decided to visit two different establishments each day.

After D days, Slava realized an important problem — some establishments had been visited by the guys more often than others. In such a case, it is impossible to speak of any fair assessment!

Anatoly proposed the following plan: continue visiting two different establishments each day, but stop when all establishments have been visited the same number of times.

It is obvious that the guys want to finish their gastronomic tour sooner (to avoid spending extra money).

Help the guys find the minimum possible number of visits to each establishment in the optimal plan.

Input

The first line contains integers n and D (2 ≤ n ≤ 2000,  1 ≤ D ≤ 2000) — the number of establishments in Bishkek and the number of days during which Slava and Anatoly have already visited some of the establishments.

Each of the following D lines contains two integers fi and si (1 ≤ fi,  si ≤ n; fi ≠ si) — the numbers of the establishments that Slava and Anatoly visited on the i-th day.

Output

In a single line, output the minimum possible number of visits to each establishment in the optimal plan.

Example
Input
5 4
1 2
2 1
3 4
2 4
Output
4
Note

First test example

One possible way to optimally finish their "tour":

  • (4, 5);
  • (1, 3);
  • (5, 1);
  • (2, 5);
  • (4, 3);
  • (3, 5).

In total, each establishment will be visited 4 times:

  • Establishment 1 visited twice before the "realization" and twice after;
  • Establishment 2 visited three times before the "realization" and once after;
  • Establishment 3 visited once before the "realization" and three times after;
  • Establishment 4 visited twice before the "realization" and twice after;
  • Establishment 5 visited zero times before the "realization" and four times after.