Задача D. С горы ≡

Условие

Однажды Андрей поднялся на гору Пидан. Когда он начал спускаться, то из-за усталости пошел не по той тропе и заблудился. Андрею известно, что все широкие тропинки, ведущие с вершины вниз, представляют собой дерево с N узлами, пронумерованными от 1 до N. Вершина горы соответствует корню дерева и имеет номер 1. Подножие горы, куда нужно попасть Андрею — самый удаленный от вершины лист дерева. Гарантируется, что такой лист ровно один.

Также Андрей знает, что на горе имеется P узких тропинок, соединяющих произвольные узлы дерева.

Помогите Андрею найти кратчайший (использующий наименьшее количество тропинок) путь от листа x, где он находится сейчас, до подножия горы, проходящий не более чем по k узким тропинкам.

Формат входного файла

Входной файл содержит целые числа N P k x. Далее следуют N − 1 пара целых чисел u_i v_i, обозначающих, что узлы u_i и v_i соединены широкой тропинкой. Далее следуют P пар целых чисел w_j t_j, обозначающих, что узлы w_j и t_j соединены узкой тропинкой.

Формат выходного файла

Требуется вывести в выходной файл единственное целое число — общее количество тропинок в кратчайшем пути от вершины с номером x до подножия горы, использующем не более k узких тропинок.

Ограничения

1 ≤ x ≤ N ≤ 10⁵, 0 ≤ k ≤ P ≤ 10,

1 ≤ u_i, v_i, w_j, t_j ≤ N, u_i ≠ v_i, w_j ≠ t_j.

Примеры тестов

11 2 2 8
1 2  1 3  2 4  2 5  3 6  3 7  5 8  7 9  7 10  10 11
5 6  6 7

5

11 2 1 8
1 2  1 3  2 4  2 5  3 6  3 7  5 8  7 9  7 10  10 11
5 6  6 7

6