Жители страны Байтландия начали строить новый город Биттаун по всем современным стандартам урбанистики. Ответственными за план города назначили знаменитых урбанистов — Адильхана Парадоксного и Темирлана Бытыхировича.
Было решено, что Биттаун будет состоять из n перекрестков. Перекрестки соединяют n − 1 двусторонних улиц. Гарантируется, что из каждого перекрестка можно добраться до всех остальных двигаясь по улицам Биттауна. На каждом перекрестке будет построен дом где будет проживать ровно одна семья.
Также было решено, что в Биттауне будет ровно две школы. Однако урбанистам все ещё нужно выбрать два перекрестка для постройки этих школ. Обратите внимание, что если на каком-то из перекрестков будет построена школа, то на нем все равно будет построен дом и будет проживать одна семья. Так же разрешается построить обе школы на одном и том же перекрестке.
Конечно же, урбанистам очень важно чтобы жители добирались до школ как можно быстрее. При этом известно что каждая семья будет посещать ближайшую к их дому школу.
Пронумеруем все перекрестки числами от 1 до n и обозначим d(v,u) как минимальное количество улиц по которым нужно пройти, чтобы добраться от перекрестка v до перекрестка u. Допустим, школы построены в перекрестках с номерами a и b. Тогда, оценка неудобства школ f(a,b) определяется как сумма расстояний от каждого дома до ближайшей школы. Более формально, f(a,b) = ∑v=1nmin[d(a,v),d(b,v)].
Оба урбаниста очень горды, и не хотят обсуждать свои планы с друг-другом. Поэтому, каждый из них будет независимо выбирать будущее положение одной из школ.
Рассмотрим 3 возможных сценария:
1. Вас делают ответственным за положения обеих школ. В этом случае, найдите минимально возможную оценку неудобства f(a,b) где 1 ≤ a,b ≤ n.
2. Темирлан Бытыхирович захотел построить школу в перекрестке a = 1, а Адильхан Парадоксный обратился за помощью к вам. Найдите минимально возможную оценку неудобства f(a,b) когда 1 ≤ b ≤ n и a = 1.
3. Адильхан Парадоксный обратился к вам за помощью, а Темирлан Бытыхирович не разгласил своих планов. В данном случае, вам нужно найти минимально возможную оценку неудобства f(a,b), где 1 ≤ b ≤ n для каждого значения a от 1 до n.
Формат входных данных
В первой строке входного файла дано одно целое число t (1 ≤ t ≤ 1000) — количество наборов входных данных.
Первая строка набора содержит два целых числа n и p (1 ≤ n ≤ 10⁵, 1 ≤ p ≤ 3) — количество перекрестков в Биттауне и сценарий, с которым вы столкнулись.
Последующие n−1 строк набора содержат пары (uᵢ,vᵢ) (1 ≤ uᵢ,vᵢ ≤ n, uᵢ ≠ vᵢ, здесь 1 ≤ i ≤ n−1) — номера перекрестков, соединенные i-й улицей.
Формат выходных данных
• Если p = 1, выведите одно целое число — минимально возможное значение f(a,b).
• Если p = 2, выведите одно целое число — минимально возможное значение f(a,b) при a = 1.
• Если p = 3, выведите n целых чисел (e₁,...,eₙ), где eᵢ — минимально возможное значение f(a,b) при a = i.