Фірма, в якій працює ваш друг, вирішила скористатися зручним моментом і купила компанію, що займається приміськими пасажирськими автобусними перевезеннями. Таким чином, фірма вашого друга розширює сферу діяльності і тепер обслуговуватиме і деякі внутрішньообласні автобусні маршрути.

Зараз керівництво фірми, і зокрема ваш друг, зайняті оптимізацією роботи цих маршрутів. Одна з основних проблем, які були виявлені, полягає в тому, що більшість автобусів, які використовуються там, дуже старі та зношені, і тому часто виходять з ладу. З метою покращення ситуації було прийнято рішення про створення мережі ремонтних станцій, які будуть розміщуватись у деяких населених пунктах області та обслуговувати інші прилеглі населені пункти.

Система доріг в області влаштована в такий спосіб. Є \(𝑁\) населених пунктів, деякі з яких з'єднані дорогами. Між кожною парою пунктів існує не більше однієї дороги, і більше того, для кожної пари населених пунктів є один спосіб дістатися з одного в інший (можливо, через проміжні селища).

У кожному населеному пункті можна розмістити ремонтну підстанцію. В принципі, фірма може розміщувати як великі станції, які навіть поодинці зможуть обслуговувати всю область, але при цьому вимагатимуть великих витрат на утримання, так і невеликі станції, які обслуговуватимуть лише прилеглі населені пункти, але обходитимуться набагато дешевше. Фірма вже визначила, що кожну станцію можна характеризувати параметром "потужність", яка може набувати значень, що є цілими додатними числами (рівна нулю потужність бути не може). Станція з потужністю \(𝑘\) обслуговуватиме населений пункт \(u\), в якому вона розташована, та всі інші населені пункти, до яких можна дістатися з \(u\), використовуючи не більше \(k\) доріг (тобто при \(𝑘 =1\), наприклад, підстанція обслуговує свій населений пункт і всі, які безпосередньо пов'язані з ним дорогою). Вартість утримання такої станції пропорційна її потужності.

Тепер перед керівництвом фірми і, зокрема, вашим другом, стоїть завдання придумати схему розташування станцій у населених пунктах області так, щоб, по-перше, кожен населений пункт обслуговувався хоча б однією станцією, а по-друге, сумарна потужність створених станцій була мінімальною .

Як показує статистика, автобуси набагато рідше ламаються на дорогах, ніж усередині населених пунктів, де вони змушені часто змінювати швидкість, зупинятися, рушати з місця, заводити двигун і т.д., тому не важливо, чи всі обслуговуються дороги — головне, щоб обслуговувалися усі населені пункти.

Формат вхідних даних

У першому рядку знаходиться одне число \(𝑁\) — кількість населених пунктів в області (\(1 \le 𝑁 \le 300\)).

Далі іде \(N−1\) рядок, що описує дороги. Кожен рядок містить два числа – номери населених пунктів, які з'єднує ця дорога. Населені пункти нумеруються від 1 до \(𝑁\).

Формат вихідних даних

У перший рядок виведіть одне число - оптимальну сумарну потужність станцій.

Далі виведіть \(𝑁\) чисел, що описують якесь оптимальне рішення. \(𝑖\) -е з цих чисел має дорівнювати потужності станції, яку у вашому рішенні треба розташувати в пункті \(𝑖\) , або 0, якщо в населеному пункті \(𝑖\) не повинна знаходитися підстанція.

Приклад вхідних даних

5
1 2
1 3
1 4
1 5

Приклад вихідних даних

1
1 0 0 0 0