В Тридесятом государстве есть N городов, все города пронумерованы числами от 1 до \(N\). Между городами построены дороги — каждая дорога соединяет между собой два города.
Царь Тридесятого государства уволил министра транспорта за то, что дороги были в очень плохом состоянии. Новый министр транспорта, чтобы не повторить судьбу своего предшественника, решил, что он будет лично контролировать состояние дорог. А именно он решил, что раз в год он лично будет объезжать все дороги.
При этом министр транспорта очень ценит свое время, и считает, что если в процессе объезда ему придется дважды проехать по какой-то дороге, то когда он будет ехать по этой дороге второй раз, ему уже не придется проверять ее состояние, и это будет недопустимой тратой времени.
Министр транспорта живет в городе номер 1, и поэтому хочет, чтобы его путешествие начиналось в этом городе. Заканчиваться путешествие должно в городе номер K, где каждый год будет проходить всегосударственное совещание по вопросам планирования ремонта дорог на следующий год.
Определите, какое минимальное количество дорог нужно построить в Тридесятом царстве в дополнение к уже существующим, чтобы можно было выполнить все требования Министра транспорта, а именно, чтобы он мог, выехав из города номер 1, проехать по каждой дороге ровно 1 раз и в итоге приехать в город номер \(K\).
Вводится число \(N\) — количество городов в Тридесятом царстве (1≤\(N\)≤100). Далее вводится число \(M\) — количество дорог в Тридесятом царстве (1≤\(M\)≤10000). Далее идет \(M\) пар чисел — каждая пара задает номера городов, соединяемых соответствующей дорогой. Все дороги двухсторонние, т.е. по дороге можно ездить в любую сторону. Между некоторыми городами может быть несколько дорог. Возможны дороги из города в него же. В последней строке входных данных находится число \(K\) — номер города, где заканчивается маршрут министра (1≤\(K\)≤\(N\)).
Выведите минимальное количество дорог, которое необходимо построить в Тридесятом царстве. Затем выведите, какие именно дороги надо построить: для каждой дороги выведите, какие города она должна соединять.
4 2 2 3 3 4 1
2 1 2 4 1
6 5 1 2 2 3 3 4 4 2 6 6 1
2 1 6 2 6
2 4 1 2 1 2 1 1 1 2 2
0
Вася, решая задачи демо-версии ЕГЭ, дошел до задачи B5, которая звучит так.
«У исполнителя Калькулятор две команды:
· прибавь 3
· умножь на 4
Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4.»
Далее в задаче требовалось получить из числа 3 число 57 не более, чем за 6 команд. Однако Вася заинтересовался, как можно для произвольных чисел \(a\) и \(b\) построить программу наименьшей длины получения числа \(b\) из числа \(a\).
Напишите программу, которая по заданным числам \(a\) и \(b\) вычислит наименьшее количество команд Калькулятора, которое нужно, чтобы получить из \(a\) число \(b\).
Вводятся два натуральных числа, не превышающих 1000 — \(a\) и \(b\).
Выведите наименьшее число команд, которое нужно, чтобы получить из \(a\) число \(b\). Если число \(b\) получить нельзя, выведите –1 (минус 1).
3 57
5
43 57
-1
10 10
0
В неориентированном связном графе \(N\) вершин и \(M\) ребер, каждое из которых имеет вес, выражающийся натуральным числом (разные ребра могут иметь разные веса). В графе нет петель (т.е. ребер, ведущих из вершины в нее саму) и кратных ребер (т.е. между любыми двумя вершинами не более одного ребра).
Весом пути из одной вершины до другой называется сумма весов ребер, по которым этот путь проходит. Кратчайшим путем между двумя вершинами называется путь минимального возможного веса между этими вершинами. Считается, что длина кратчайшего пути от вершины до неё самой равна нулю.
В этом графе вычислили длины кратчайших путей между всеми парами вершин и записали их в виде таблицы. В этой таблице число на пересечении \(i\)-ой строки \(j\)-ого столбца равно длине кратчайшего пути из вершины номер \(i\) в вершину номер \(j\).
После этого исходный граф был утерян.
Напишите программу, которая по заданной таблице кратчайших расстояний восстановит какой-нибудь граф, которому эта таблица могла бы соответствовать, либо установит, что графа описанного в условии вида, которому могла бы соответствовать данная таблица, не существует.
Вводятся числа \(N\) и \(M\), а затем таблица кратчайших расстояний (\(1 ≤ N ≤ 300, 0 ≤ M ≤ 1000\), элементы таблицы кратчайших путей — целые неотрицательные числа, не превышающие \(10^6\)).
Если такой граф существует, выведите в первой строке сообщение YES, в противном случае — сообщение NO. Если граф существует, то начиная со второй строки выведите \(M\) троек чисел, описывающих ребра. Каждое ребро описывается номерами вершин, которые оно соединяет, и весом. Веса всех ребер не должны превышать \(10^6\).
4 4 0 1 2 5 1 0 3 4 2 3 0 7 5 4 7 0
YES 1 2 1 1 3 2 2 4 4 1 4 5
3 2 0 1 1 1 0 1 1 1 0
NO
Петя занимается разведением дракончиков. У него есть \(M\) зеленых дракончиков и \(K\) желтых. У Пети есть \(N\) двухместных аквариумов для дракончиков и \(M+K–2N\) одноместных.
Петя, понаблюдав некоторое время за своими дракончиками, установил, что некоторые пары дракончиков не могут жить вместе (будучи помещенными в один аквариум они тут же начинают драться), а также некоторые дракончики совершенно не переносят одиночества и поэтому не могут жить в одноместном аквариуме.
Петя хочет с использованием своих знаний так разместить дракончиков по аквариумам, чтобы в каждом двухместном аквариуме обязательно был один зеленый дракончик и один желтый, и при этом драконы, не переносящие одиночества, обязательно были бы помещены в двухместный аквариум, и в двухместном аквариуме никогда не оказывалось бы двух драконов, которые не могут жить вместе.
Вводятся числа \(M, K, N\) (\(M ≥ 1, K ≥ 1, N ≥ 0, N ≤ M, N ≤ K, M + K ≤ 200\)). Будем считать, что зеленые дракончики пронумерованы числами от \(1\) до \(M\), а желтые – числами от \(M+1\) до \(M+K\).
Далее идет число \(T\) (\(0 ≤ T ≤ MK\)) – количество пар дракончиков, про которых известно, что они не переносят друг друга. Далее идет \(T\) пар чисел, описывающих номера не переносящих друг друга дракончиков (первое число каждой пары описывает зеленого дракончика, второе – желтого). Далее идет число \(Q\) (\(0 ≤ Q ≤ M + K\))– количество дракончиков, не переносящих одиночества. Далее идет \(Q\) чисел, задающих номера этих драконов.
В случае если разместить дракончиков по аквариумам требуемым образом нельзя, выведите единственное слово NO. В противном случае первая строка должна содержать YES. В следующие \(N\) строк выведите \(N\) пар чисел, задающих номера дракончиков, которых нужно поместить в двухместные аквариумы.
2 1 1 1 1 3 1 1
NO
2 2 1 1 1 3 1 2
YES 2 4
Одна из Сверхсекретных организаций, чье название мы не имеем право разглашать, представляет собой сеть из \(N\) подземных бункеров, соединенных равными по длине туннелями, по которым из любого бункера можно добраться до любого другого (не обязательно напрямую). Связь с внешним миром осуществляется через специальные засекреченные выходы, которые расположены в некоторых из бункеров.
Организации понадобилось составить план эвакуации персонала на случай экстренной ситуации. Для этого для каждого из бункеров необходимо узнать, сколько времени потребуется для того, чтобы добраться до ближайшего из выходов. Вам, как специалисту по таким задачам, поручено рассчитать необходимое время для каждого из бункеров по заданному описанию помещения Сверхсекретной организации. Для вашего же удобства бункеры занумерованы числами от 1 до \(N\).
Сначала вводятся два натуральных числа \(N\), \(K\) (\(1\) ≤ \(N\) ≤ 100000, \(1\) ≤ \(K\) ≤ \(N\)) — количество бункеров и количество выходов соответственно.
Далее через пробел записаны \(K\) различных чисел от \(1\) до \(N\), обозначающих номера бункеров, в которых расположены выходы.
Потом идёт число \(M\) (1 ≤ \(M\) ≤ 100000) — количество туннелей. Далее вводятся M пар чисел – номера бункеров, соединенных туннелем. По каждому из туннелей можно двигаться в обе стороны. В организации не существует туннелей, ведущих из бункера в самого себя, зато может существовать более одного туннеля между парой бункеров.
Выведите \(N\) чисел, разделенных пробелом — для каждого из бункеров минимальное время, необходимое чтобы добраться до выхода. Считайте, что время перемещения по одному туннелю равно \(1\).
3 1 2 3 1 2 3 1 2 3
1 0 1
10 2 10 8 9 6 7 7 5 5 8 8 1 1 10 10 3 3 4 4 9 9 2
1 4 1 2 1 3 2 0 3 0