Задано дерево из $$$n$$$ вершин. Изначально ни одна из вершин дерева не окрашена.

Вы можете выполнять следующую операцию: выбрать две любые вершины $$$u$$$ и $$$v$$$ (можно в том числе выбирать $$$u=v$$$) и покрасить все вершины на пути между ними (включая концы) в цвет $$$i$$$, где $$$i$$$ — номер операции, которую вы выполняете (то есть первая операция красит в цвет $$$1$$$, вторая — в цвет $$$2$$$, и так далее). Если какая-то вершина на пути уже была покрашена ранее, ее цвет меняется на новый.

Назовем раскраску дерева полной, если для каждой вершины была проведена хотя бы одна операция, окрашивающая ее.

Ваша задача — посчитать два значения:

• минимальное количество операций, необходимое для получения полной раскраски;
• количество различных полных раскрасок, которые можно получить за минимальное количество операций (две раскраски считаются различными, если существует хотя бы одна такая вершина $$$v$$$, что цвет $$$v$$$ в первой раскраске отличается от цвета $$$v$$$ во второй раскраске).