Đường đi trên đồ thị bù

General
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho $N$ thành phố đánh số từ $1$ đến $N$. Giữa mọi cặp thành phố khác nhau đều có đường bay thẳng hai chiều, ngoại trừ $M$ cặp thành phố bị cấm bay.

Mỗi chuyến bay mất $1$ giờ. Hãy tìm thời gian ngắn nhất để đi từ thành phố $1$ đến tất cả các thành phố từ $1$ đến $N$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N, M$.

$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả một cặp thành phố không có đường bay thẳng.

Dữ liệu ra

In ra $N$ số nguyên trên một dòng, số thứ $i$ là thời gian ngắn nhất để đi từ $1$ đến $i$ (hoặc -1 nếu không thể đến $i$).

Ví dụ
Input Output
4 3
1 2
1 3
2 4
0 3 2 1
4 3
1 2
1 3
1 4
0 -1 -1 -1
Giới hạn
  • $1 \le N \le 2 \cdot 10^5$
  • $0 \le M \le 2 \cdot 10^5$
  • $1 \le u, v \le N$, $u \ne v$
Draft saved