eolymp
bolt
Try our new interface for solving problems
Məsələlər

Строки в дереве

Строки в дереве

Zaman məhdudiyyəti 4 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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

Также дана строка S. Соответствует ли она какому-либо простому пути в данном дереве?

Длина строки и размер дерева не превышают 3·10^5.

Giriş verilənləri

Первая строка содержит заданную строку s. Следующая строка содержит количество вершин в дереве n. Следующие n-1 строк описывают рёбра дерева в виде u, v, c, где u и v - вершины дерева, а c - символ, написанный на ребре.

Çıxış verilənləri

В первой строке выведите YES, если такой путь существует, и NO в противном случае.

Если путь существует, то выведите пару вершин, путь между которыми образует заданную строку.

Nümunə

Giriş verilənləri #1
abc
4
1 2 c
4 3 a
2 4 b
Çıxış verilənləri #1
YES
1 3