Строки в дереве
Дано дерево. Дерево - это связный граф без циклов. На каждом ребре дерева написана строчная латинская буква. Между каждыми двумя вершинами существует ровно один простой путь, то есть путь по рёбрам дерева, проходящий через каждую вершину не более одного раза. Каждому пути соответствует строка, которая получается, если идти по этому пути и читать буквы на рёбрах в пути её следования. Путь можно проходить начиная с любого его конца.
Также дана строка S. Соответствует ли она какому-либо простому пути в данном дереве?
Длина строки и размер дерева не превышают 3·10^5.
Входные данные
Первая строка содержит заданную строку s. Следующая строка содержит количество вершин в дереве n. Следующие n-1 строк описывают рёбра дерева в виде u, v, c, где u и v - вершины дерева, а c - символ, написанный на ребре.
Выходные данные
В первой строке выведите YES, если такой путь существует, и NO в противном случае.
Если путь существует, то выведите пару вершин, путь между которыми образует заданную строку.