Задача №114802. Три тропинки
В городе, в котором живет Вася, есть парк, в котором \(n\) лужаек, соединенных \(m\) тропинками. По каждой тропинке можно ходить в обоих направлениях. Лужайки, соединенные тропинкой, будем называть соседними.
Вход в парк находится около лужайки номер один. Васины родители очень беспокоятся за его безопасность, поэтому разрешают ему играть только на лужайке, соседней с лужайкой у входа. На самой лужайке у входа обычно слишком много народа, поэтому на ней играть нельзя.
Но Васе кажется скучным просто перейти на соседнюю лужайку по тропинке. Вместо этого, он, начав с лужайки с номером один, проходит ровно по трем различным тропинкам, а затем уже играет на лужайке, на которой оказался. Разумеется, Вася не нарушает правил, установленных родителями, и заканчивает свой путь на лужайке, соседней с входом в парк.
Вася любит разнообразие, поэтому каждый день он хочет выбирать новый путь, по которому он раньше не ходил. Помогите Васе определить, сколько у него есть вариантов начать свой путь на лужайке с номером один, пройти ровно по трем различным тропинкам и оказаться на лужайке, соседней с стартовой лужайкой.
В первой строке даны числа \(n\) и \(m\) — количество лужаек и количество тропинок, соответственно (\(1 \leq n \leq 100\,000\), \(1 \leq m \leq 200\,000\)).
В следующих \(m\) строках заданы пары лужаек, соединенных тропинками. Любые две лужайки соединены не более чем одной тропинкой. Никакая тропинка не соединяет лужайку саму с собой.
Выведите количество вариантов пути, по которому может пройти Вася.
10 14 1 5 2 5 5 6 2 3 1 3 2 4 4 6 1 6 1 7 7 8 8 1 1 10 9 10 9 8
4
3 3 1 2 2 3 3 1
0