Рядки у дереві#2925
Дано дерево, тобто зв'язний граф без циклів. Кожне ребро в дереві підписане малою латинською літерою. Для будь-якої пари вершин існує рівно один простий шлях між ними: шлях через ребра дерева, який відвідує кожну вершину не більше одного разу. Кожному такому шляху відповідає певний рядок, який утворюється зчитуванням літер на ребрах уздовж шляху. Шлях можна проходити, починаючи з будь-якого з його кінців.
Вам дано рядок . Чи існує в дереві простий шлях, вздовж якого, прочитавши підписи ребер, утворюється цей рядок?
Довжина рядка і розмір дерева не перевищують 3\cdot 10^5.
У першому рядку задано рядок . У другому рядку — число вершин у дереві . Кожен з наступних n-1 рядків описує ребро дерева у форматі , де і — вершини дерева, а — символ на ребрі між ними.
Виведіть у першому рядку , якщо такий шлях існує, і — інакше.
Якщо шлях існує, також виведіть пару вершин, між якими шлях утворює даний рядок.
Приклад 1