Архівне дерево#13102

Архівне дерево

1 секунда
256 мегабайтів

Архів складається з папок, пронумерованих від до . Деякі пари папок безпосередньо пов'язані посиланнями, всього таких посилань n - 1, і з будь-якої папки можна перейти за посиланнями до будь-якої іншої; інакше кажучи, папки та посилання утворюють дерево. Папка є кореневою.

Для кожної папки v \ne s її батьківською папкою називається сусід на шляху від до кореневої папки, а називається підпапкою своєї батьківської папки.

Кожній папці треба дати назву f_v — додатне ціле число. За правилами архіву назви мають задовольняти такі умови:

Короткі назви легше набирати, тому адміністратор хоче, щоб найбільша назва в архіві була якомога меншою. Знайдіть мінімально можливе значення \max\limits_{1 \le v \le n} f_v.

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 5 \cdot 10^5) — кількість тестових випадків.

Перший рядок кожного тестового випадку містить два цілі числа та (1 \le s \le n \le 5 \cdot 10^5) — кількість папок і номер кореневої папки. Кожен із наступних n - 1 рядків містить два цілі числа та (1 \le u, v \le n, u \ne v) — папки, пов'язані посиланням. Гарантується, що посилання утворюють дерево.

Сума за всіма тестовими випадками не перевищує 5 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число — мінімально можливу найбільшу назву.

Приклади

Приклад 1

Loading
Loading

Примітка

У першому тестовому випадку коренева папка — , і вона має підпапки , і . Папка має підпапки і , а папка — підпапки і . Одне з оптимальних призначень назв:

  • f_4 = 1;

  • f_1 = 1, f_2 = 2, f_8 = 3;

  • f_3 = 1, f_5 = 2;

  • f_6 = 2, f_7 = 4.

Можна показати, що найбільша назва не може бути меншою за .

У другому тестовому випадку папки утворюють ланцюжок 1 - 2 - 3 - 4 - 5 з кореневою папкою посередині. Папки і є підпапками кореневої папки, тому їм потрібні різні назви. Наприклад, f_1 = f_2 = f_3 = 1 і f_4 = f_5 = 2, тож відповідь — .

У третьому тестовому випадку є лише коренева папка, і f_1 = 1.