EduBrick

E. Где входит не столько, сколько выходит

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

Ориентированный граф задан списком рёбер. Найдите все вершины, у которых полустепень захода не равна полустепени исхода.

Такие вершины мешают графу иметь эйлеров цикл — но это тема будущих занятий; сейчас достаточно их найти.

Формат ввода

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

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

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

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

Далее по одной вершине на строке в порядке возрастания номера: сам номер и разность «заход минус исход».

Примеры

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