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

Автор:О. Ларькина   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ x ≤ N ≤ 105, 0 ≤ k ≤ P ≤ 10,
1 ≤ ui, vi, wj, tj ≤ N, ui ≠ vi, wj ≠ tj.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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
2
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

0.100s 0.009s 15