Trong khoảng sân trong của một ngôi nhà bỏ hoang, bạn đã tìm thấy một cuốn sách cổ được giấu rất kỹ, hé lộ bí mật được giữ kín nhất của thành phố Bonn. Sâu bên dưới thành phố là một hệ thống gồm ~N~ hang động, được nối với nhau bằng ~M~ kênh nước. Trong mỗi kênh nước có một dòng chảy ma thuật một chiều có thể nhanh chóng đưa một chiếc thuyền đi dọc theo kênh. Hiện tại, hệ thống hang động có đúng một lối ra, nằm ở hang ~N-1~.

Bạn vô cùng hào hứng với khám phá của mình và nóng lòng muốn thám hiểm các hang động! Tuy nhiên, trong hệ thống hang động có một con quỷ troll sinh sống, thích trêu chọc những vị khách không mời mà đến. Con quỷ có một sức mạnh phép thuật hạn chế – mà nó có thể sử dụng nhiều nhất một lần trong chuyến thám hiểm của bạn – để thay đổi hệ thống hang động và khiến bạn khó đến lối ra hơn.

Chuyến thám hiểm hệ thống hang động của bạn sẽ gồm một chuỗi các lượt. Mỗi lượt diễn ra như sau:

1. Đầu tiên, con quỷ được chọn có sử dụng sức mạnh phép thuật của nó hay không. Nếu có, phép thuật của nó thực hiện tất cả những việc sau:

   • đảo ngược hướng dòng chảy ma thuật trong mọi kênh: ~a \rightarrow b~ lập tức đổi thành ~b \rightarrow a~;

   • đóng lối ra ở hang ~N-1~; và

   • mở một lối ra mới ở hang ~0~.

2. Sau đó, bạn chọn một dòng chảy ma thuật chảy ra từ hang hiện tại và dùng thuyền của mình để đi đến một hang khác. Để đơn giản, ta gọi một lần dùng thuyền như vậy là một "bước di chuyển".

Ngoài ra, bất cứ khi nào bạn ở cùng hang với lối ra, bạn sẽ ngay lập tức dùng lối ra đó để rời khỏi hệ thống hang động. Lưu ý rằng điều này thậm chí có thể xảy ra ngay trong một lượt nếu bạn đang ở hang ~0~ và con quỷ quyết định sử dụng sức mạnh phép thuật của nó.

Mục tiêu của bạn là rời khỏi hệ thống hang động nhanh nhất có thể để kịp tham dự lễ bế mạc EGOI. Mục tiêu của con quỷ hoàn toàn ngược lại; nó muốn giữ bạn trong các hang động của nó lâu nhất có thể. Con quỷ luôn biết vị trí của bạn và sẽ chọn thời điểm sử dụng sức mạnh phép thuật sao cho có lợi nhất cho mục tiêu của nó.

Xét riêng từng hang ~c~ (~0 \le c \le N-2~) với tình huống bạn bắt đầu ở hang ~c~. Với mỗi tình huống này, hãy xác định số bước di chuyển nhỏ nhất mà bạn có thể bảo đảm đến được một lối ra từ hang ~c~, bất kể con quỷ chọn sử dụng sức mạnh của nó vào lúc nào.

Giả sử phép thuật không được sử dụng, từ hang ~0~ có thể đi đến mọi hang, và từ mọi hang đều có thể đi đến hang ~N-1~.

Input

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên ~N~ và ~M~, trong đó ~N~ là số hang động và ~M~ là số kênh nước. ~M~ dòng tiếp theo của dữ liệu vào, mỗi dòng chứa hai số nguyên ~a_i~ và ~b_i~, biểu diễn một kênh hiện tại có thể dùng để đi từ hang ~a_i~ đến hang ~b_i~. Không có kênh nào nối một hang với chính nó. Với mỗi cặp hang, có nhiều nhất một kênh theo mỗi hướng.

Output

In ra một dòng chứa ~N-1~ số nguyên, trong đó số nguyên thứ ~i~, ~0 \le i \le N-2~, là số bước di chuyển nhỏ nhất mà bạn có thể bảo đảm đến được một lối ra nếu bắt đầu ở hang ~i~.

Lưu ý rằng bạn không in ra thời gian cho hang ~N-1~ (vì bạn sẽ lập tức thoát ra khỏi hang này).

Scoring

• ~2 \le N \le 200000~.

• ~1 \le M \le 500000~.

• ~0 \le a_i,b_i \le N-1~ và ~a_i \ne b_i~.

• Trước khi đảo ngược hướng, từ hang ~0~ có thể đi đến tất cả các hang, và từ tất cả các hang đều có thể đi đến hang ~N-1~.

Lời giải của bạn sẽ được kiểm tra trên một số nhóm test, mỗi nhóm có một số điểm nhất định. Mỗi nhóm test chứa một tập hợp các test. Để nhận được điểm của một nhóm test, bạn cần giải đúng tất cả các test trong nhóm đó.

Subtask	Điểm	Ràng buộc
1	~12~	~M=N-1~, ~a_i=i~ và ~b_i=i+1~ với mọi ~i~. Nói cách khác, hệ thống hang động tạo thành một đường đi ~0 \rightarrow 1 \rightarrow 2 \rightarrow \dots \rightarrow N-1~
2	~15~	Với mỗi ~0 \le i \le N-2~, có một kênh trực tiếp từ hang ~i~ đến hang ~N-1~. Lưu ý rằng có thể có thêm các kênh khác.
3	~20~	~N,M \le 2000~
4	~29~	Sau khi rời khỏi một hang bất kỳ, không thể quay trở lại hang đó (cho đến khi các hướng bị đảo ngược). Nói cách khác, các kênh tạo thành một đồ thị có hướng không có chu trình.
5	~24~	Không có giới hạn gì thêm

Sample Input 1

5 6
0 1
1 2
1 3
2 4
3 4
0 3

Sample Output 1

2 2 2 1

Sample Input 2

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

Sample Output 2

2 1 2 3 2 4

Sample Input 3

2 1
0 1

Sample Output 3

1

Sample Input 4

6 8
0 1
4 0
1 2
2 3
3 5
0 4
4 5
2 0

Sample Output 4

2 4 3 3 1

Notes

Với ví dụ thứ nhất, xét trường hợp bạn bắt đầu ở hang ~1~. Vì không biết khi nào các hướng sẽ bị đảo ngược, bạn nên bắt đầu di chuyển về phía lối ra ở hang ~4~. Bạn có thể đi qua hang ~2~ hoặc hang ~3~. Đi qua hang ~3~ là lựa chọn tốt hơn ở đây, vì nếu các hướng bị đảo ngược khi bạn đang ở đó, bạn sẽ có một kênh để đi thẳng từ hang ~3~ đến hang ~0~, nơi bạn sẽ thoát khỏi hệ thống hang động.

Cụ thể hơn, chỉ có ba khả năng về thời điểm con quỷ quyết định sử dụng sức mạnh phép thuật của nó:

• Nếu con quỷ dùng sức mạnh ngay khi bạn đang ở hang ~1~, bạn có thể đi thẳng từ hang ~1~ đến hang ~0~ và thoát ra.

• Nếu con quỷ dùng sức mạnh sau khi bạn đi từ hang ~1~ đến hang ~3~, bạn có thể đi thẳng từ hang ~3~ đến hang ~0~ và thoát ra.

• Nếu con quỷ quyết định không dùng sức mạnh trong cả hai tình huống trên, bạn sẽ đi từ hang ~3~ đến hang ~4~ và thoát ra.

Trong khả năng thứ nhất, bạn chỉ cần thực hiện một bước di chuyển; trong mỗi khả năng còn lại, bạn thực hiện hai bước. Điều này có nghĩa là đáp án cho trường hợp này là ~\max(1,2,2)=2~.

Lưu ý rằng nếu bạn chọn đi từ hang ~1~ đến hang ~2~, con quỷ có thể buộc bạn thực hiện ba bước di chuyển.

Ví dụ thứ nhất và thứ hai thỏa mãn ràng buộc của các nhóm test ~3~, ~4~ và ~5~. Ví dụ thứ ba thỏa mãn ràng buộc của tất cả các nhóm test. Ví dụ thứ tư thỏa mãn ràng buộc của các nhóm test ~3~ và ~5~.

Ghi công và giấy phép

Bài toán này có nguồn gốc từ EGOI 2025 (Olympic Tin học nữ châu Âu), Ngày 2, được tổ chức tại Bonn, Đức.

• Đề bài gốc: Currents

• Tác giả: Brian Lee Jun Siang.

• Chủ sở hữu bản quyền: Olympic Tin học nữ châu Âu 2025.

• Tài liệu chính thức: Đề bài và lời giải · Dữ liệu kiểm thử, trình chấm và các bản dịch

• Giấy phép: Creative Commons Ghi công – Chia sẻ tương tự (CC BY-SA), theo siêu dữ liệu chính thức của bài toán. Siêu dữ liệu không chỉ rõ phiên bản giấy phép.

• Các thay đổi: Dịch sang tiếng Việt và định dạng lại cho ClueOJ.

Bản dịch này được phân phối theo cùng các điều khoản CC BY-SA áp dụng cho bài toán gốc.

ClueOJ không có quan hệ liên kết với EGOI hoặc ban tổ chức EGOI 2025, cũng không được các bên này chứng thực.