Задачи по графам

Задача 1:

Дан граф с n вершинами, пронумерованных от 1 до n. Определите, является ли граф деревом или нет.
Входные данные:
Первая строка содержит два целых числа n (2 ≤ n ≤ 10^5) и m (1 ≤ n ≤ 10^5) - количество вершин и ребер соответственно.
Далее следует m строк. i-я из них содержит два целых числа v_i и u_i (1 ≤ v_i, u_i ≤ n, v_i ≠ u_i) — номера вершин, между которыми есть ребро.
Выходные данные:
Выведите yes, если граф является деревом, иначе no.

Пример:

Ввод	Вывод
5 4 1 2 1 3 5 2 2 4	yes
5 5 1 2 3 1 2 4 5 2 1 5	no

Задача 2:

Дан граф с n вершинами, пронумерованных от 1 до n. Выведите все вершины, у которых имеются более 1 предка. Предок вершины v — это вершина, из которой исходит ребро, заходящее в вершину v.
Входные данные:
Первая строка содержит два целых числа n (2 ≤ n ≤ 10^5) и m (1 ≤ n ≤ 10^5) - количество вершин и ребер соответственно.
Далее следует m строк. i-я из них содержит два целых числа v_i и u_i (1 ≤ v_i, u_i ≤ n, v_i ≠ u_i) — номера вершин, между которыми есть ребро.
Выходные данные:
Выведите номера вершин, у которых более одного предка, если таких вершин нет, то выведите -1.

Пример:

Ввод	Вывод
5 6 1 2 1 3 4 3 4 5 5 3 2 4	4 5
7 5 1 2 3 4 5 3 1 3 6 7	-1

Задача 3:

Дан граф с n вершинами, пронумерованных от 1 до n. Найдите самую отдаленную вершину от вершины k. Гарантируется, что такая вершина есть.
Входные данные:
Первая строка содержит три целых числа n (2 ≤ n ≤ 10^5), m (1 ≤ n ≤ 10^5) и k (1 ≤ n ≤ 10^5) - количество вершин ,ребер и вершина k соответственно.
Далее следует m строк. i-я из них содержит два целых числа v_i и u_i (1 ≤ v_i, u_i ≤ n, v_i ≠ u_i) — номера вершин, между которыми есть ребро.
Выходные данные:
Выведите номер вершины, которая находится дальше всех от вершины k.

Пример:

Ввод	Вывод
8 6 2 1 2 7 8 4 3 1 3 3 5 6 5	6