Недавно на главном кыргызском сайте для олимпиад по программированию появился новый функционал — разделение задач на отдельные тома.
Тома нумеруются целыми числами, начиная с 1. Внутри каждого тома задачи нумеруются целыми числами от 0 до n.
Таким образом, каждой задаче соответствует пара чисел (v, k) — номер тома и номер внутри тома, соответственно.
Также внутри каждой задачи появилась кнопка «перейти к следующей»:
- Если k < n, то кнопка открывает задачу (v, k + 1).
- В ином случае кнопка открывает задачу (v + 1, 0).
В данный момент вы находитесь на странице задачи (a, b). Вас заинтересовало, сколько нажатий кнопки потребуется, чтобы добраться до задачи (c, d)?
В первой строке содержится целое число n (1 ≤ n ≤ 1000) — максимально возможный номер задачи внутри тома.
Во второй строке содержатся два целых числа a и b (1 ≤ a ≤ 1000, 0 ≤ b ≤ n) — номер задачи, на которой вы находитесь в данный момент.
В третьей строке содержатся два целых числа c и d (1 ≤ c ≤ 1000, 0 ≤ d ≤ n) — номер задачи, до которой вы хотите добраться.
Гарантируется, что из задачи (a, b) возможно добраться до (c, d):
- либо a < c;
- либо a = c и b < d.
В единственной строке выведите целое число — необходимое количество нажатий на кнопку «перейти к следующей», после которого вы из задачи (a, b) попадёте в задачу (c, d).
12
2 5
2 8
3
8
3 4
4 5
10
14
2 11
4 1
20
Первый тестовый пример
Последовательность нажатий (2, 5) — (2, 6) — (2, 7) — (2, 8) — всего 3 нажатия.
Второй тестовый пример
Последовательность нажатий:
- (3, 4) — (3, 8) — всего 4 нажатия;
- (3, 8) — (4, 0) — 1 нажатие;
- (4, 0) — (4, 5) — ещё 5 нажатий.
Всего 10 нажатий.
Профессор Термитов изучает $$$n$$$ новых гипотез научного мира.
Известно, что $$$i$$$-я гипотеза имеет показатель невозможности $$$p_i$$$. Профессор поверит в достаточно правдоподобную гипотезу, но откажется верить в выглядящую совсем фантастично.
Поверит профессор или нет в $$$i$$$-ю гипотезу, зависит от его уровня фантазии $$$f_{i - 1}$$$:
- если $$$p_i \le f_{i - 1} + c$$$, то профессор верит в гипотезу ($$$c$$$ — параметр кредита доверия).
В таком случае его уровень фантазии станет равным $$$f_{i} = \max{(f_{i - 1}, p_i)}$$$.
- если же $$$p_i \gt f_{i - 1} + c$$$, то профессор не верит в гипотезу.
В таком случае его уровень фантазии станет равным $$$f_{i} = f_{i - 1} - \max{(d, p_i - f_{i - 1} - c)}$$$, где $$$d$$$ — параметр степени разочарованности.
Также известно, что ни одно из значений $$$f_0 \dots f_n$$$ не может быть отрицательным.
Вы случайно стали свидетелем данного процесса через лабораторное стекло. По итогу вы видели все реакции коллеги $$$r_i$$$ (поверил / не поверил), но самих гипотез вы не слышали.
Теперь вам интересно найти любой набор $$$p_i$$$, приводящий к заданной последовательности реакций $$$r_i$$$ (с учетом ограничений на $$$f_i$$$).
Если существует несколько подходящих наборов — выведите любой набор с минимально возможным $$$\max{(p_i)}$$$.
В первой строке содержатся целые числа $$$n$$$, $$$f_0$$$, $$$c$$$, $$$d$$$ $$$(1 \le n \le 3 \cdot 10^5, \, 1 \le f_0, \, c, \, d \le 5000)$$$ — количество гипотез, исходное значение уровня фантазии профессора, а также параметры кредита доверия и степени разочарованности, соответственно.
Во второй строке содержится строка $$$r$$$ $$$(|r| = n; r_i \in [T, F])$$$ — реакции профессора на $$$i$$$-ю гипотезу.
Если $$$r_i = T$$$, то профессор поверил в $$$i$$$-ю гипотезу; если же $$$r_i = F$$$, то $$$i$$$-я гипотеза была признана слишком неправдоподобной.
В первой строке выведите YES, если последовательность $$$p$$$ возможно построить, и NO, если такой последовательности не существует.
Если последовательность существует, выведите ещё две строки.
Во второй строке выведите целое число $$$pmax$$$ — максимальное значение среди всех значений $$$p_i$$$.
В третьей строке выведите через пробел $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ $$$(0 \le p_i \le pmax)$$$ — подходящие значения показателей невозможности.
5 3 2 1 TFFTT
YES 6 1 6 5 2 0
3 4 1 2 FFF
NO
Первый тестовый пример
Покажем, как показанный в тесте набор $$$p_i$$$ приводит к заданному набору реакций.
- $$$p_1 \le f_0 + c$$$ ($$$1 \le 3 + 2$$$), поэтому профессор поверил в гипотезу $$$1$$$.
Его фантазия осталась равной $$$f_1 = \max{(3, 1)} = 3$$$.
- $$$p_2 \gt f_1 + c$$$ ($$$6 \gt 3 + 2$$$), поэтому профессор не поверил в гипотезу $$$2$$$.
Его фантазия стала равной $$$f_2 = 3 - \max{(1, 6 - 3 - 2)} = 3 - 1 = 2$$$.
- $$$p_3 \gt f_2 + c$$$ ($$$5 \gt 2 + 2$$$), поэтому профессор не поверил в гипотезу $$$3$$$.
Его фантазия стала равной $$$f_3 = 2 - \max{(1, 5 - 2 - 2)} = 2 - 1 = 1$$$.
- $$$p_4 \le f_3 + c$$$ ($$$2 \le 1 + 2$$$), поэтому профессор поверил в гипотезу $$$4$$$.
Его фантазия стала равной $$$f_4 = \max{(1, 2)} = 2$$$.
- $$$p_5 \le f_4 + c$$$ ($$$0 \le 2 + 2$$$), поэтому профессор поверил в гипотезу $$$5$$$.
Его фантазия стала равной $$$f_5 = \max{(2, 0)} = 2$$$.
Можно показать, что нельзя построить набор с $$$pmax \lt 6$$$ — это наименьшее значение, при котором $$$r_2 = F$$$.
Также обратите внимание, что приведенный в ответе набор не является единственным возможным.
Например, следующие наборы тоже являются одними из возможных ответов на задачу:
- $$$[3, 6, 5, 0, 2]$$$;
- $$$[0, 6, 5, 3, 1]$$$;
- и т.д.
Второй тестовый пример
- $$$r_1 = F$$$, значит $$$p_1 \gt f_0 + c$$$ ($$$p_1 \gt 4 + 1$$$).
$$$p_1$$$, приводящая к наименьшему понижению фантазии, равна $$$6$$$ или $$$7$$$.
В таком случае $$$f_1 = 4 - \max{(2, 6 - 4 - 1)} = 4 - 2 = 2$$$.
- $$$r_2 = F$$$, значит $$$p_2 \gt f_1 + c$$$ ($$$p_2 \gt 2 + 1$$$).
$$$p_2$$$, приводящая к наименьшему понижению фантазии, равна $$$4$$$ или $$$5$$$.
В таком случае $$$f_2 = 2 - \max{(2, 5 - 2 - 1)} = 2 - 2 = 0$$$.
- $$$r_3 = F$$$, значит $$$p_3 \gt f_2 + c$$$ ($$$p_3 \gt 0 + 1$$$).
$$$p_3$$$, приводящая к наименьшему понижению фантазии, равна $$$2$$$ или $$$3$$$.
В таком случае $$$f_3 = 0 - \max{(2, 2 - 0 - 1)} = 0 - 2 = -2$$$.
На каждом шаге мы старались минимизировать понижении уровня фантазии, но всё равно пришли к отрицательному значению.
Отсюда следует, что не существует никакого набора $$$p$$$, приводящего к заданной последовательности реакций.
Павел точно знает — завтра всегда лучше, чем вчера.
Он решил это доказать с помощью геометрии.
Для этого Павел рассмотрел n последовательных дней и каждому сопоставил точку на плоскости (xi, yi).
Он считает, что день i + 1 лучше дня i, если выполнено одно из двух условий:
- либо xi < xi + 1;
- либо xi = xi + 1, но yi < yi + 1.
Павел не уверен лишь в одном — правильно ли он выбрал систему координат для своих расчетов? Он уверен, что для поиска верной системы координат можно использовать только повороты и/или отражения.
Помогите Павлу — найдите любую прямоугольную (ортогональную) систему координат, в которой каждый следующий день будет лучше предыдущего.
В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество проанализированных Павлом дней.
В каждой из следующих n строк содержится по два целых числа xi и yi ( - 105 ≤ xi, yi ≤ 105) — точка, сопоставленная Павлом i-му дню.
В первой строке выведите YES, если такая прямоугольная система координат существует, и NO в противном случае.
Если искомая система координат существует, выведите ещё две строки.
Во второй строке выведите через пробел два целых числа Xx и Yx (|Xx|, |Yx| ≤ 109;|Xx| + |Yx| > 0) — координаты вектора, сонаправленного с осью Ox новой системы координат.
В третьей строке выведите через пробел два целых числа Xy и Yy (|Xy|, |Yy| ≤ 109;|Xy| + |Yy| > 0) — координаты вектора, сонаправленного с осью Oy новой системы координат.
Вектора (Xx, Yx) и (Xy, Yy) должны быть перпендикулярны между собой.
Если существует несколько вариантов ответа, выведите любой.
9
3 3
2 3
3 2
1 3
2 2
3 1
1 2
2 1
1 1
YES
-1 -1
1 -1
4
1 1
1 2
2 2
2 1
NO
1
100000 100000
YES
-100000 100000
-100000 -100000
2
0 0
0 0
NO
Первый тестовый пример
Сначала рассмотрим точки, сопоставленные дням, и найденные вектора в оригинальной системе координат:
Теперь покажем эти же точки в системе координат, основанной на найденных векторах:
Координаты точек после перехода в новую систему координат:
- (3, 3) — ( - 3, 0);
- (2, 3) — ( - 2.5, - 0.5);
- (3, 2) — ( - 2.5, 0.5);
- (1, 3) — ( - 2, - 1);
- (2, 2) — ( - 2, 0);
- (3, 1) — ( - 2, 1);
- (1, 2) — ( - 1.5, - 0.5);
- (2, 1) — ( - 1.5, 0.5);
- (1, 1) — ( - 1, 0).
Видно, что каждая следующая точка «лучше» предыдущей в новой системе координат.
Известен набор событий, заданных массивом целых чисел ai.
Вы считаете, что из события с номером i можно было предвидеть событие с номером j, если верны оба условия:
- ai < aj;
- наибольший общий делитель ai и aj отличен от 1.
Цепочка событий, где каждое следующее можно было предвидеть из предыдущего, вы называете заговором.
Докажите всем, что ваша теория заговора не является лишь теорией — найдите заговор, состоящий из наибольшего количества событий.
В первой строке содержится целое число n (1 ≤ n ≤ 106) — количество событий.
Во второй строке содержится n целых чисел a1, a2, ..., an (1 ≤ aj ≤ 2·106) —параметры событий.
В первой строке выведите целое число k (1 ≤ k ≤ n) — максимально возможный размер заговора.
Во второй строке выведите через пробел k целых чисел pj (1 ≤ pj ≤ n) — номера этих событий в порядке предвидения.
В случае, если заговоров максимального размера несколько, выведите любой из них.
5
1 2 3 4 5
2
2 4
8
8 7 10 3 6 5 3 11
4
4 5 1 3
3
2 2 2
1
1
Первый тестовый пример
Последовательность [2;4] является заговором, так как из события a2 = 2 можно предсказать a4 = 4:
- 2 < 4;
-
(
— наибольший общий делитель).
Второй тестовый пример
Последовательность [4;5, 1, 3] является заговором, так как:
- a4 = 4;
- a5 = 6: 3 < 6,
; - a1 = 8: 6 < 8,
; - a3 = 10: 8 < 10,
.
Третий тестовый пример
В данном примере заговор из двух любых событий невозможен, так как все ai равны между собой.
В то же время любое событие формально является заговором само по себе, поэтому размер ответа всегда не менее 1.
Медер и Кылычбек вместе организуют тренировочные сборы для лучших спортивных программистов Кыргызстана.
Они уже объявили n учебных тем, с которыми участники сборов должны ознакомиться в процессе.
Но есть проблема — необходимо составить расписание сборов таким образом, чтобы оба преподавателя были довольны.
Во-первых, не все темы можно рассказывать друг за другом. Всего известно k связей учебных тем (fi, si) таких, что тему si можно рассказывать сразу после fi, причем тема si всегда строго сложнее темы fi.
Формально: гарантируется, что если есть связь (f, s), то не существует никакой последовательности связей, позволяющих после прочтения s рассказать f.
Во-вторых, у каждого преподавателя есть своя любимая тема, которую он предпочитает рассказывать в первый день сборов.
Ни с какой другой темы ни Медер, ни Кылычбек не согласятся начинать свою часть сборов.
Также гарантируется, что не существует связей, позволяющих прочитать любимую тему преподавателей после другой темы.
В-третьих, итоговое расписание должно включать каждую из n заявленных тем хотя бы один раз (но оба преподавателя могут рассказать одну и ту же тему при необходимости).
Помогите Медеру и Кылычбеку — найдите для каждого преподавателя подходящую последовательность учебных тем, чтобы в итоге выполнялись все три описанных выше условия.
В первой строке содержатся целые числа n и m (2 ≤ n ≤ 2·105, 1 ≤ m ≤ 2·105) — количество тем, планируемых для сборов, и количество связок тем.
Во второй строке содержатся целые числа tM и tK (1 ≤ tM, tK ≤ n, tM ≠ tK) — номера любимых тем Медера и Кылычбека, соответственно.
В каждой из следующих m строк содержится по два целых числа fi и si (1 ≤ fi, si ≤ n, fi ≠ si;si ≠ tM;si ≠ tK) — темы, входящие в i-ю связь (тему si можно прочитать после прочтения fi).
Гарантируется, что если есть связь (f, s), то не существует никакой последовательности связей, позволяющих после прочтения s рассказать f.
В первой строке выведите YES, если Медер и Кылычбек смогут прочитать все n тем, и NO в противном случае.
Если сборы получится провести, то выведите ещё четыре строки.
Во второй строке выведите целое число dM — количество тем, которые прочитает Медер, начав с темы tM.
В третьей строке выведите через пробел dM целых чисел — последовательность тем, которые прочтёт Медер, начиная с темы tM.
В четвёртой строке выведите целое число dK — количество тем, которые прочитает Кылычбек, начав с темы tK.
В пятой строке выведите через пробел dK целых чисел — последовательность тем, которые прочтёт Кылычбек, начиная с темы tK.
6 7
1 2
1 3
1 4
2 3
2 4
3 5
4 5
3 6
YES
3
1 3 6
3
2 4 5
6 6
1 3
1 2
2 4
3 4
3 5
5 6
4 6
YES
4
1 2 4 6
3
3 5 6
6 5
1 2
1 3
2 3
3 4
3 5
3 6
NO
5 5
1 2
1 3
2 3
3 4
2 4
4 5
YES
4
1 3 4 5
4
2 3 4 5
Первый тестовый пример
- Медер начал со своей любимой темы 1, перешёл к теме 3 и закончил свои лекции на теме 6.
- Кылычбек начал со своей любимой темы 2, перешёл к теме 4 и закончил свои лекции на теме 5.
Суммарно преподаватели рассказали все n = 6 тем.
Второй тестовый пример
Медер и Кылычбек оба прочитали тему 6. Расписание, где тема 6 прочитана только одним из двух преподавателей, тоже было бы корректным.
Третий тестовый пример
Медер и Кылычбек не смогут прочитать за время сборов темы 4, 5 и 6 — только любые две из них.
Четвёртый тестовый пример
Либо Медер, либо Кылычбек могли прочитать только свою любимую тему и остановиться на этом — второй преподаватель всё равно прочитал бы все остальные темы сборов.
Артём организует Чемпионат Кыргызстана по программированию.
Соревнование пройдёт во временном промежутке [S;F].
Для помощи в организации соревнования Артём набрал n волонтёров. Известно, что i-й волонтёр сможет помочь во временном промежутке [bi, ei].
Артём понимает, что может случиться всякое, поэтому для каждого момента t времени он ввёл «индекс помощи» H(t) — количество волонтёров, которые в момент времени t могут помочь ему решить ту или иную проблему.
Формально говоря, индекс помощи H(t) равен количеству волонтёров таких, что bi ≤ t ≤ ei.
Артём продумывает различные сценарии развития событий, поэтому для каждого значения h 
[1... n] он хочет знать, какое суммарное время в течение чемпионата индекс помощи H(t) будет строго меньше h.
В первой строке содержится целое число n (1 ≤ n ≤ 3·105) — количество волонтёров.
Во второй строке содержатся целые числа S и F (1 ≤ S < F ≤ 109) — начало и конец временного промежутка чемпионата.
В каждой из следующих n строк содержится по два целых числа bi и ei (1 ≤ bi < ei ≤ 109) — начало и конец временного отрезка, когда доступен i-й волонтёр.
Выведите n чисел t1, t2, ..., tn, где th — суммарное время в течение чемпионата, когда «индекс помощи» строго меньше h.
5
10 20
5 12
16 19
15 25
8 14
13 17
0 3 9 10 10
Первый тестовый пример
- Индекс помощи никогда не будет 0 в течение чемпионата, откуда t1 = 0.
- Индекс помощи 1 будет в промежутках [12;13], [14;15] и [19;20] — суммарная длительность промежутков равна 3, откуда t2 = 3 + 0 = 3.
- Индекс помощи 2 будет в промежутках [10;12], [13;14], [15;16] и [17;19] — суммарная длительность равна 6, откуда t3 = 6 + 3 + 0 = 9.
- Индекс помощи 3 будет в промежутке [16;17] — суммарная длительность равна 1, откуда t4 = 1 + 6 + 3 + 0 = 10.
- Индекс помощи никогда не будет равен 4, поэтому t5 = 10 аналогично t4.
Айдар готовится к очередной международной олимпиаде.
По мнению Айдара, успех выступления зависит от двух показателей — скорости печати кода и скорости придумывания идей.
Айдар знает, что в данный момент его скорость печати кода равна Sp, а скорость придумывания идей — Sm.
Каждый день Айдар будет тратить Tp минут на тренировку печати, что каждые два дня будет увеличивать его скорость печати на Dp.
Аналогично, каждый день Айдар будет тратить Tm минут на тренировку придумывания идей, что каждые два дня будет увеличивать скорость придумывания на Dm.
Обратите внимание, что переход «количества в качество» не мгновенный, поэтому после одного дня тренировок Айдар не ощутит прироста на 
.
Также Айдар может проводить «усиленные» тренировки:
- Айдар может тренировать скорость печати 4·Tp минут вместо Tp — в таком случае он ощутит прирост навыка печати на Dp уже после одного дня.
- Аналогично, Айдар может тренировать скорость придумывания 4·Tm минут вместо Tm — в таком случае он ощутит прирост навыка придумывания на Dm уже после одного дня.
- Айдар может проводить «усиленные» тренировки сразу по обоим показателям, если посчитает это необходимым.
Айдар будет считать себя достаточно готовым, если обе скорости (печати и придумывания) будут не ниже величины E.
Айдар хочет выйти на достаточный уровень готовности как можно раньше (но в то же время не хочет тратить излишних усилий), поэтому просит вас определить:
- минимальное количество дней, за которые Айдар может добиться достаточного уровня готовности;
- минимальное суммарное количество минут, которое он сможет при этом потратить на подготовку (при условии достижения минимального количества дней).
В первой строке содержатся целые числа Sp, Sm, Dp, Dm, Tp, Tm, E (1 ≤ Sp, Sm, E ≤ 108, 1 ≤ Dp, Dm ≤ 105, 1 ≤ Tp, Tm ≤ 108) — начальные значения навыков Айдара, показатели изменения навыков, необходимое количество минут на обычную тренировку и достаточный предел готовности, соответственно.
В первой строке выведите целое число — минимальное количество дней, за которые Айдар может добиться достаточного уровня готовности.
Во второй строке выведите целое число — минимальное суммарное количество минут, которое он сможет при этом потратить на подготовку (при условии достижения минимального количества дней).
1 3 2 1 3 10 18
15
672
3 1 1 2 1000 1 3
1
1004
Первый тестовый пример
Легко заметить, что в оптимальном решении Айдару придётся делать усиленные тренировки на придумывание каждый день.
Итого пройдёт 
дней усиленных тренировок придумывания — всего 15·4·10 = 600 минут.
Для практики печати Айдар может применить следующее распределение ресурсов:
- 3 дня проводить усиленные тренировки — таким образом он может поднять свой навык на 3·2 = 6, затратив 3·4·3 = 36 минут;
- остальные 12 дней проводить обычные тренировки — таким образом он поднимет свой навык ещё на
, затратив 12·3 = 36 минут.
Всего Айдар потратит в таком случае 600 + 72 = 672 минуты.
Обратите внимание, что Айдар не успеет уложиться в 15 дней, если сделает только две усиленные тренировки печати:
- за 2 дня усиленных тренировок он наберёт 2·2 = 4 навыка;
- за остальные 13 дней обычных тренировок Айдар поднимет навык ещё на
.
Суммарно получится 1 + 4 + 12 = 17 навыка, чего не хватит для достаточного уровня готовности.
Анатолий договорился со Славой вместе доехать до нового автовокзала.
Ребята договорились поехать вместе либо с остановки A, либо со следующей остановки B.
Известно, что Слава уже сел на нужный автобус и едет в направлении «A 
B» (то есть сначала он проедет остановку A, а уже потом остановку B).
Анатолий прибыл на остановку B раньше Славы, но быстро понял, что ошибся с прогнозом погоды — пошел сильный ливень с пронизывающим холодным ветром.
Чтобы не замерзнуть, Анатолий решил сесть в первый подъехавший автобус и доехать до остановки A, чтобы подождать там. Но на остановке A теплее не стало, поэтому Анатолий запрыгнул в автобус, направлявшийся к остановке B...
Опишем процесс более формально:
- Если Анатолий находится на остановке B, то он поедет к остановке A только в случае, если успеет приехать туда строго раньше, чем туда прибудет автобус со Славой.
- Если Анатолий находится на остановке A, то он поедет к остановке B только в случае, если успеет приехать туда строго раньше, чем автобус со Славой прибудет к остановке A.
Известно, что все автобусы проезжают расстояние между остановками A и B (в одну и другую сторону) за d минут.
Также известно, что если Анатолий выйдет из автобуса во время t, то сесть в следующий автобус он сможет не ранее t + 1 (надо дорогу перейти, как минимум).
Зная время прибытия всех автобусов на остановку B, определите:
- на какой остановке Анатолий сядет в автобус, в котором едет Слава;
- на скольких автобусах успеет прокатиться Анатолий до момента встречи.
В первой строке содержатся через пробел целые числа n, m, d (1 ≤ n, m ≤ 106, 1 ≤ d ≤ 106) — количество автобусов, едущих к остановке B со стороны остановки A, количество автобусов, едущих к остановке B с противоположной стороны и время проезда между остановками A и B, соответственно.
Во второй строке содержится через пробел n целых чисел a1, a2, ..., an (0 ≤ a1 < a2 < ... < an ≤ 106) — моменты времени, в которые к остановке B подъезжают автобусы, едущие со стороны остановки A.
Слава едет в последнем из этих автобусов.
В третьей строке содержится m целых чисел b1, b2, ..., bm (0 ≤ b1 < b2 < ... < bm ≤ 106) — моменты времени, в которые к остановке B подъезжают автобусы, едущие с противоположной стороны.
В первой строке выведите через пробел символ и целое число:
- символ A, если Анатолий сядет в автобус со Славой на остановке A, или символ B, если Анатолий сядет на остановке B;
- количество автобусов, на которых к этому моменту проедет Анатолий.
5 6 4
8 15 24 26 30
1 7 10 16 22 27
A 3
Первый тестовый пример
Слава приедет на остановку B в момент времени 30, а на остановку A соответственно — в 30 - 4 = 26.
- В момент времени 1 Анатолий сядет в автобус, следующий от B к A.
- В момент времени 1 + 4 = 5 Анатолий доедет до остановки A.
- В момент времени 15 - 4 = 11 Анатолий сядет в автобус, следующий от A к B.
- В момент времени 15 Анатолий доедет до остановки B.
- В момент времени 16 Анатолий сядет в автобус, следующий от B к A.
- В момент времени 16 + 4 = 20 Анатолий доедет до остановки A.
- Обратите внимание, что Анатолий не сможет сесть на автобус до остановки B в момент 24 - 4 = 20, так как на пересадку требуется минимум одна минута.
- Также обратите внимание, что Анатолий не сможет сесть на автобус до остановки B в момент 26 - 4 = 22, так как в таком случае он прибудет на остановку B в момент времени 26 — Слава уже подъедет к остановке A в этот момент.
- Соответственно, Анатолий дождётся Славу на остановке A, проехав на трёх автобусах.
Когда Анатолий и Слава приехали в Бишкек, они решили как можно скорее изучить его самые интересные кафе и рестораны.
Для этого ребята решили каждый день посещать два различных заведения.
Спустя D дней Слава осознал важную проблему — какие-то заведения были посещены ребятами чаще, чем другие. В таком случае нельзя говорить ни о какой справедливой оценке!
Анатолий предложил следующий план: продолжить каждый день посещать по два различных заведения, но остановиться, когда все заведения будут посещены одинаковое количество раз.
Очевидно, что ребятам хочется закончить гастрономический тур пораньше (чтобы не тратить лишние деньги).
Помогите ребятам найти минимально возможное количество посещений каждого заведения в оптимальном плане.
В первой строке содержатся целые числа n и D (2 ≤ n ≤ 2000, 1 ≤ D ≤ 2000) — количество заведений в Бишкеке и количество дней, в которые Слава и Анатолий уже посетили какие-то из заведений.
В каждой из следующих D строк содержится по два целых числа fi и si (1 ≤ fi, si ≤ n; fi ≠ si) — номера заведений, которые посетили Слава и Анатолий в i-й день.
В единственной строке выведите минимально возможное количество посещений каждого заведения в оптимальном плане.
5 4
1 2
2 1
3 4
2 4
4
Первый тестовый пример
Один из возможных способов оптимально закончить свой «поход»:
- (4, 5);
- (1, 3);
- (5, 1);
- (2, 5);
- (4, 3);
- (3, 5).
Суммарно каждое заведение будет посещено по 4 раза:
- Заведение 1 посещено два раза до «осознания» и два — после;
- Заведение 2 посещено три раза до «осознания» и один — после;
- Заведение 3 посещено один раз до «осознания» и три — после;
- Заведение 4 посещено два раза до «осознания» и два — после;
- Заведение 5 посещено ноль раз до «осознания» и четыре — после.