eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Рядки у дереві

Рядки у дереві

Ліміт часу 4 секунди
Ліміт використання пам'яті 256 MiB

Задано дерево. Дерево - це зв'язний граф без циклів. На кожному ребрі дерева написано рядкову латинську літеру. Між кожними двома вершинами існує рівно один простий шлях, тобто шлях по ребрам дерева, який проходить через кожну вершину не більше одного разу. Кожному шляху відповідає рядок, який отримується, якщо йти по цьому шляху і читати букви на ребрах на цьому. Шлях можна проходити починаючи з довільного його кінця.

Також задано рядок S. Чи відповідає він якомусь простому шляху у заданому дереві?

Довжина рядка та розмір дерева не перевищує 3·10^5.

Вхідні дані

Перший рядок містить заданий рядок s. Наступний рядок містить кількість вершин у дереві n. Наступні n-1 рядків описують ребра дерева у вигляді u, v, c, де u та v - вершини дерева, а c - символ, написаний на ребрі.

Вихідні дані

У першому рядку виведіть YES, якщо такий шлях існує, і NO у протилежному випадку.

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

Приклад

Вхідні дані #1
abc
4
1 2 c
4 3 a
2 4 b
Вихідні дані #1
YES
1 3