JOI có đồ thị vô hướng đơn với \(N\) thành phố và \(M\) con đường. Bitaro bắt đầu tại thành phố \(s\). Một hành trình có độ dài ít nhất \(1\), có thể đi qua một thành phố nhiều lần, và được biểu diễn bằng dãy thành phố \(v_1,v_2,\ldots,v_l\) sao cho \(v_1=s\), hai thành phố liên tiếp có cạnh nối, và các bước đi luân phiên tăng rồi giảm theo nhãn: ở bước lẻ \(v_j<v_{j+1}\), ở bước chẵn \(v_j>v_{j+1}\).

Ví dụ, \((2)\) và \((1,4,1,5,3)\) thỏa mãn điều kiện luân phiên tăng giảm, còn \((3,2)\) thì không.

Với từng \(s=1,2,\ldots,N\), hãy đếm số thành phố không xuất hiện trong bất kỳ hành trình hợp lệ nào bắt đầu tại \(s\).

Dữ liệu vào

Dòng đầu chứa \(N,M\). \(M\) dòng tiếp theo chứa \(A_i,B_i\), mô tả một cạnh với \(A_i<B_i\).

Dữ liệu ra

In \(N\) dòng. Dòng \(s\) là số thành phố không thể đến được khi bắt đầu tại \(s\).

Ràng buộc

• \(1 \le N \le 300000\) và \(0 \le M \le 300000\).
• \(1 \le A_i<B_i\le N\).
• Không có cạnh trùng nhau.
• Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(12\) điểm: \(N\le1000\), đồ thị có \(M=N-1\) cạnh và tồn tại một hoán vị \(P\) của \(1,2,\ldots,N\) sao cho có cạnh nối \(P_i\) với \(P_{i+1}\) với mọi \(1\le i<N\).
2. \(19\) điểm: \(N,M\le1000\).
3. \(15\) điểm: đồ thị có \(M=N-1\) cạnh và tồn tại một hoán vị \(P\) của \(1,2,\ldots,N\) sao cho có cạnh nối \(P_i\) với \(P_{i+1}\) với mọi \(1\le i<N\).
4. \(17\) điểm: mọi đỉnh có bậc không quá \(2\).
5. \(37\) điểm: không có ràng buộc thêm.

Ví dụ

4 4
1 2
1 3
1 4
3 4

0
3
0
3

2 0

1
1

4 3
1 3
3 4
2 4

2
1
1
3

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

1
1
3
5
3
5

Nguồn

JOI 2025/2026 - Vòng loại 2, bài Bitaro's Travel 3.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.