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
Коментарі