Ученые в тайной химической лаборатории в Хорватии изучают химические связи в недавно обнаруженном веществе инопланетного происхождения. Имеющаяся в распоряжении ученых порция вещества состоит из N молекул, соединенных между собой N - 1 ковалентными связями, и все молекулы объединены этими связями (не обязательно напрямую) в единую сеть.
Так как вещество нестабильное, в каждой молекуле регулярно возникают импульсы, перемещающиеся по веществу через существующие связи в обоих направлениях. Ученые собираются стабилизировать вещество, направив ковалентные связи (то есть, дав импульсам возможность путешествовать по ним между молекулами лишь в одном направлении). Показатель нестабильности вещества определяется длиной максимального пути, который может пройти импульс в нем, и ученые хотят сделать эту величину как можно меньше.
Помогите ученым создать вещество с минимальным показателем нестабильности, указав необходимое направление ковалентных связей.
Первая строка содержит одно целое число N ( 2 ≤ N ≤ 100000 ). Каждая из последующих N - 1 строк содержит по два целых числа a i и b i ( 1 ≤ a i , b i ≤ N ), которые показывают что молекулы с номерами a i и b i соединены ковалентной связью.
Выведите N - 1 строку, каждая из которых должна содержать 1 если ковалентная связь должна быть направлена от a i к b i или 0 в противном случае.
Решения, в которых N ≤ 20 , будут оцениваться в 30 баллов.
3 1 2 2 3
0 1
4 2 1 1 3 4 1
1 0 1
Мирко получил в подарок на свой день рождения квадратный стол N x N , где в каждой клетке записано неотрицательное целое число. К сожалению, некоторые числа кажутся Мирко слишком большими, поэтому он собирается положить на стол K фишек домино, которые закроют некоторые слишком большие числа. Точнее, он собирается положить фишки домино в соответствии со следующими правилами:
1. Каждая фишка домино покрывает две клетки, соседних по строчке или столбцу..
2. Фишки домино не накладываются друг на друга (но могут соприкасаться).
3. Сумма чисел на всех видимых (непокрытых) клетках минимальна.
Ваша задача - определить минимально возможную сумму чисел на видимых клетках. Тесты к задаче таковы, что на поле всегда можно положить K не накладывающихся друг на друга фишек домино.
Первая строка содержит два целых числа: N ( 1 ≤ N ≤ 2000 ) - размер стола, и K ( 1 ≤ K ≤ 8 ) - количество фишек домино. Каждая из следующих N строк содержит N целых чисел (в диапазоне [0, 1000]) - числа в соответствующих клетках поля.
Выведите единственное целое число - минимально возможную сумму чисел в клетках после установки фишек домино.
Решения, работающие при K ≤ 5 , будут оцениваться в 70 баллов.
3 1 2 7 6 9 5 1 4 3 8
31
4 2 1 2 4 0 4 0 5 4 0 3 5 1 1 0 4 1
17