Автор: | О. Ларькина | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
Однажды Андрей поднялся на гору Пидан. Когда он начал спускаться, то из-за усталости пошел не по той тропе и заблудился. Андрею известно, что все широкие тропинки, ведущие с вершины вниз, представляют собой дерево с N узлами, пронумерованными от 1 до N. Вершина горы соответствует корню дерева и имеет номер 1. Подножие горы, куда нужно попасть Андрею — самый удаленный от вершины лист дерева. Гарантируется, что такой лист ровно один.
Также Андрей знает, что на горе имеется P узких тропинок, соединяющих произвольные узлы дерева.
Помогите Андрею найти кратчайший (использующий наименьшее количество тропинок) путь от листа x, где он находится сейчас, до подножия горы, проходящий не более чем по k узким тропинкам.
Входной файл содержит целые числа NPkx. Далее следуют N−1 пара целых чисел uivi, обозначающих, что узлы ui и vi соединены широкой тропинкой. Далее следуют P пар целых чисел wjtj, обозначающих, что узлы 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 |
|
|
2 |
|
|