EduBrick

N. Рёбра компонент

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

Неориентированный граф задан списком рёбер. Для каждой компоненты связности выведите количество её вершин и количество её рёбер.

Компоненты нумеруются в том порядке, в котором их находит обход при переборе стартовых вершин от 1 к nn. Каждое ребро принадлежит ровно одной компоненте; петли и кратные рёбра считаются.

Формат ввода

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

Далее идут mm строк с рёбрами.

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

В первой строке — количество компонент.

Далее по строке на компоненту: число вершин и число рёбер.

Примеры

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