G. Истоки и стоки
3000 мс · 256 МБ · всё или ничего
Постройте конденсацию и посчитайте в ней истоки — компоненты без входящих рёбер — и стоки — компоненты без исходящих.
Это те же полустепени, что в первом занятии по графам, только считаются они не по вершинам, а по компонентам, и кратные рёбра между одной парой компонент считаются за одно.
Числа не случайные: именно из них складывается ответ следующей задачи. Граф из одной компоненты даёт один исток и один сток, и он же — единственный случай, когда исток и сток могут совпасть.
Формат ввода
Первая строка содержит числа () и ().
Далее идут строк с рёбрами. Возможны кратные рёбра и петли.
Формат вывода
Два числа: количество истоков и количество стоков.
Примеры
ввод
4 4 2 1 3 2 2 3 4 3
вывод
1 1
ввод
5 0
вывод
5 5
Войдите, чтобы отправлять решения.