EduBrick

J. Изоморфизм деревьев

1000 мс · 256 МБ · всё или ничего

Даны два дерева из nn вершин без выделенного корня. Изоморфны ли они?

Формат ввода

В первой строке - число nn (1≤n≤1051 \le n \le 10^5).

В следующих n−1n - 1 строках - рёбра первого дерева, затем в n−1n - 1 строках - рёбра второго.

Формат вывода

Выведите YES, если деревья изоморфны, и NO иначе.

Примеры

ввод
6
1 3
2 3
3 4
4 5
4 6
1 2
1 5
1 6
2 4
2 3
вывод
YES
ввод
4
1 2
1 3
1 4
1 2
2 3
3 4
вывод
NO
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.