Đường đi trên đồ thị bù
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề 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$
Community Discussion