Под расстоянием между двумя вершинами в графе будем понимать длину кратчайшего пути между ними в рёбрах. Для данной вершины s определите максимальное расстояние от неё до другой вершины неориентированного графа.
В первой строке дано количество вершин n (1 ≤ n ≤ 105) и рёбер m (0 ≤ m ≤ 105). Далее в m строках описаны рёбра графа. Каждое ребро описывается номерами двух вершин u и v (1 ≤ u, v ≤ n). В последней строке дан номер вершины s (1 ≤ s ≤ n).
Гарантируется, что граф связный и что в нём нет петель и кратных рёбер.
Выведите длину наибольшего пути от s до одной из вершин графа.
|
5 4 2 1 4 5 4 3 3 2 2 |
3 |
|
3 3 3 1 1 2 2 3 1 |
1 |
|
6 8 6 1 1 3 5 1 3 5 3 4 6 5 5 2 6 2 4 |
3 |