Задача №113814. Древесный путь
Вам дано дерево с N вершинами, обозначенными целыми положительными числами от 1 до N . Кроме того, вам даны M пар вершин из дерева в формате ( a 1 , b 1 ), ( a 2 , b 2 ), ..., ( a m , b m ).
Вам нужно направить каждый ребро дерева так, чтобы для каждой данной вам пары вершин ( a i , b i ) был путь от a i до b i или от b i до a i . Сколько существует различных способов достичь этого? Поскольку ответ может быть большим, выведите его по модулю 10 9 + 7 .
Первая строка содержит 2 числа N и M ( 1 ≤ N , M ≤ 3·10 5 ) — число вершин в дереве и числа заданных пар вершин.
В следующих N - 1 строках идёт описание дерева. Каждая содержит по 2 числа X и Y ( 1 ≤ X , Y ≤ N ) и означает, что вершины X и Y соединены ребром.
Следующие M строк описывают заданные пары вершин. В i -й из них даны числа a i и b i . Гарантируется, что нет одинаковых пар вершин. Т.е. нет таких i и j , что a i = b i и a j = b j , или a i = b j и a j = b i .
В одной строке выведите единственное число — ответ на задачу.
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для принятия на проверку.
1. Бамбук - дерево, где любая вершина с номером i > 1 связана ребром с вершиной с номером i - 1 .
4 1 1 2 2 3 3 4 2 4
4
7 2 1 2 1 3 4 2 2 5 6 5 5 7 1 7 2 6
8
4 3 1 2 1 3 1 4 2 3 2 4 3 4
0