EduBrick

G. Истоки и стоки

3000 мс · 256 МБ · всё или ничего

Постройте конденсацию и посчитайте в ней истоки — компоненты без входящих рёбер — и стоки — компоненты без исходящих.

Это те же полустепени, что в первом занятии по графам, только считаются они не по вершинам, а по компонентам, и кратные рёбра между одной парой компонент считаются за одно.

Числа не случайные: именно из них складывается ответ следующей задачи. Граф из одной компоненты даёт один исток и один сток, и он же — единственный случай, когда исток и сток могут совпасть.

Формат ввода

Первая строка содержит числа nn (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5) и mm (0≤m≤2⋅1050 \le m \le 2 \cdot 10^5).

Далее идут mm строк с рёбрами. Возможны кратные рёбра и петли.

Формат вывода

Два числа: количество истоков и количество стоков.

Примеры

ввод
4 4
2 1
3 2
2 3
4 3
вывод
1 1
ввод
5 0
вывод
5 5
Войдите, чтобы отправлять решения.