Để quản lý việc gặm cỏ, Farmer John xây đường một chiều khắp trang trại. Có $N$ đồng đánh số $1..N$, mỗi đường nối hai đồng. Đường từ $X$ đến $Y$ chỉ cho đi từ $X$ đến $Y$, không ngược lại.

Bessie thích ăn cỏ ở nhiều đồng nhất có thể. Mỗi sáng bắt đầu ở đồng $1$, đi qua một chuỗi rồi trở về $1$. Cô tối đa hóa số đồng khác nhau vì chỉ ăn cỏ ở mỗi đồng một lần dù thăm nhiều lần.

Cô không thích giới hạn một chiều vì giảm số đồng. Nếu phá luật và đi ngược tối đa một lần, cô ăn được bao nhiêu? Hãy tính số đồng khác nhau lớn nhất trên đường bắt đầu và kết thúc ở $1$, với tối đa một lượt ngược chiều. Cả chuyến chỉ được ngược một lần, kể cả cùng một đường cũng không thể đi ngược hai lần.

Dữ liệu vào

Dòng đầu chứa số đồng $N$ và số đường $M$ ($1 \leq N, M \leq 100,000$).

$M$ dòng tiếp cho hai mã khác nhau $X$, $Y$ của đường từ $X$ đến $Y$. Không có đường lặp lại.

Dữ liệu ra

In một dòng số đồng khác nhau lớn nhất trên lộ trình từ $1$ về $1$ với tối đa một lượt ngược chiều.

Ví dụ

Dữ liệu vào 1

7 10
1 2
3 1
2 5
2 4
3 7
3 5
3 6
6 5
7 2
4 7

Dữ liệu ra 1

6

Ghi chú

Hình ASCII của ví dụ:

v---3-->6
7   |\  |
^\  v \ |
| \ 1  \|
|  \|   v
|   v   5
4<--2---^

Có thể thăm $1,2,4,7,2,5,3,1$ bằng cách đi ngược giữa $5$ và $3$. Ở $3$, không thể đến $6$ nếu không đi ngược thêm một đường.

Tác giả bài toán: Mark Gordon, 2015