13072. Максимум по мінімуму


Відправити розв'язок

Бали: 100
Time limit: 1.0s
Memory limit: 500M

Authors:
Problem type
Allowed languages
C++, Java, Pascal, Python

Дано орієнтований незважений граф. У ньому необхідно знайти вершину, найкоротша відстань від якої до заданої максимальна.

Формат вхідних даних

У першому рядку вхідного файлу містяться три натуральні числа \(N\), \(M\) і \(S\) (\(1 \leqslant S \leqslant N \leqslant 5000\), \(1 \leqslant M \leqslant 20\,000\)) - кількість вершин та ребер у графі та номер заданої вершини відповідно.

Далі в \(M\) рядках перераховані ребра графа. Кожне ребро задається парою чисел. номерами початкової та кінцевої вершин відповідно.

Формат вихідних даних

Вивести одне ціле число - шукану найкоротшу відстань.

Приклад вхідних даних

3 5 3
1 2
2 1
3 1
2 3
3 3

Приклад вихідних даних

2

Коментарі

Ще немає коментарів.