Пожалуйста обьясните как сделать задачу на питоне

15-й век на дворе. В стране есть n аулов, которые пронумерованы от 1 до n, включительно. Они соединены n−1 дорогами. i-я дорога соединяет xi-й и yi-й ауылы. Гарантируется, что можно добраться от любого аула до любого другого по дорогам. Есть m торговых маршрутов. i-й торговый маршрут начинается в ai-ом ауле и заканчивается в bi-ом. Маршрут считается хорошим, если на пути есть аул с рынком. Изначально ни в каком ауле нет рынка. Мы хотим выбрать некоторые аулы и открыть в них рынки, чтобы все торговые маршруты считались хорошими. Так как в казне не так много денег, мы хотим открыть рынки в минимальном количестве аулов. Найдите это минимальное количество.

Входные данные
В первой строке задано два целых числа n и m (1≤n,m≤10⁵). В следующих n−1 строках заданы по два числа xi и yi (1≤xi, yi≤n) задающих дороги. В следующих m строках заданы по два числа ai и bi (1≤ai, bi≤n) задающих маршруты.

Выходные данные
Выведите ответ на задачу.

Система оценки
Данная задача содержит 5 подзадач, в которых выполняются следующие ограничения:

n, m≤10. Оценивается в 12 баллов.
n, m≤10³. Оценивается в 15 баллов.
У каждого аула есть не более двух соседних аулов. Оценивается в 17 баллов.
n≤10⁵, m≤7. Оценивается в 17 баллов.
n, m≤10⁵. Оценивается в 39 баллов.
Примеры
входные данные
5 2
1 5
4 5
5 3
2 4
2 1
5 3
выходные данные
1
входные данные
5 2
4 5
5 2
5 3
1 3
3 1
2 4
выходные данные
2
входные данные
8 4
1 2
1 7
8 7
8 5
8 4
4 6
3 6
2 1
8 2
8 4
3 6
выходные данные
3

0

Сообщение от JOHN51141 Пожалуйста обьясните как сделать задачу на питоне

Похоже на поиск точек сочленения в неориентированной графе: Cutpoints. Могу, правда, ошибаться...

0