Дай дорогу!#11516
Дано неорієнтоване дерево, що складається з вершин, з'єднаних n - 1 двосторонніми ребрами. У цьому дереві знаходиться потяг: його голова розташована у вершині , а хвіст — у вершині . Вагони потяга займають всі вершини на простому шляху між вершинами та .
Вам потрібно визначити, чи може потяг розвернутися, тобто перемістити голову у вершину, де був хвіст, і перемістити хвіст у вершину, де була голова. Рухи потяга обмежені структурою дерева.
За одну операцію потяг може перемістити голову в сусідню вершину, яка не зайнята потягом у поточний момент. Коли це відбувається, хвіст потяга переміщується на одну вершину ближче до голови, зберігаючи незмінну довжину потяга. Аналогічно, потяг може перемістити хвіст у сусідню вершину, яка не зайнята потягом у поточний момент. У цьому випадку голова потяга переміщується на одну вершину ближче до хвоста.
Визначте, чи може потяг розвернутися за допомогою певної послідовності операцій.
У першому рядку знаходиться єдине ціле число — кількість тестів. Наступні рядки містять описи тестів.
У першому рядку кожного тесту знаходяться три цілі числа n, a, b\:(2 \le n \le 10^5, 1 \le a, b \le n, a \ne b).
Кожен з наступних n - 1 рядків містить два цілі числа u_i, v_i\:(1 \le u_i, v_i \le n, u_i \ne v_i), що позначають ребро між вершинами u_i та v_i. Гарантується, що дані ребра утворюють дерево.
Гарантується, що сума по всіх наборах вхідних даних не перевищує 10^6.
Для кожного тесту виведіть "YES", якщо потяг може розвернутися, і "NO" інакше.
Приклад 1