| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 147 | 12 | 12 | 11.650% |
Операторам склада необходимо переместить тяжелую коробку с использованием специального погрузчика. Склад можно схематически представить как $n$ комнат, соединенных $m$ коридорами. От любой комнаты можно добраться до любой другой, перемещаясь по коридорам. Комнаты пронумерованы от 1ドル$ до $n$. Коридор номер $i$ непосредственно соединяет комнаты с номерами $u_i$ и $v_i,ドル по коридору можно перемещаться в обоих направлениях.
Погрузчик может поднимать и опускать коробку, а также, если он не держит коробку, перемещаться по свободным комнатам и коридорам. Изначально погрузчик находится в комнате номер 1ドル,ドル и держит поднятую коробку. Погрузчику доступны следующие действия:
Пустой погрузчик перемещается между комнатами очень быстро, гораздо быстрее, чем он поднимает или опускает коробку. Поэтому будем считать, что на выполнение первого или второго действия погрузчик тратит одну единицу времени, а третье действие выполняется мгновенно. Ваша задача --- для каждой комнаты $p$ (2ドル \le p \le n$) определить, за какое минимальное время погрузчик может из изначального положения --- в первой комнате с поднятой коробкой, оказаться в комнате $p$ с поднятой коробкой. Либо определить, что это сделать невозможно.
Каждый тест состоит из нескольких наборов входных данных. В первой строке дано одно целое число $t$ (1ドル \leq t \leq 100,000円$) --- количество наборов входных данных. Далее следуют описания наборов входных данных.
В первой строке каждого набора входных данных даны два целых числа $n$ и $m$ (2ドル \leq n \leq 500,000円,ドル 1ドル \leq m \leq 500,000円$) --- количество комнат и коридоров на складе.
В следующих $m$ строках даны по два целых числа $u_i$ и $v_i$ (1ドル \leq u_i, v_i \leq n,ドル $u_i \neq v_i$) --- номера комнат, соединенных $i$-м коридором. Гарантируется, что каждая пара комнат, соединенных коридором, упомянута ровно один раз. Гарантируется, что если все комнаты свободны, от любой комнаты можно добраться до любой другой, перемещаясь по коридорам.
Обозначим за $\sum n$ сумму $n,ドル а за $\sum m$ сумму $m$ по всем наборам входных данных в одном тесте. Гарантируется, что $\sum n \leq 500,000円,ドル $\sum m \leq 500,000円$.
Для каждого набора входных данных выведите $n - 1$ чисел: $i$-е из них должно быть равно минимальному количеству подъемов и опусканий коробки, которые нужно сделать погрузчику, чтобы оказаться в комнате $i + 1$ с поднятой коробкой. Если это сделать невозможно, то $i$-е число должно быть равно $-1$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 16 | $\sum n \leq 1000,ドル $\sum m \leq 2000$ |
| 2 | 18 | $\sum n \leq 1000,ドル $\sum m \leq 100,000円$ |
| 3 | 14 | $\sum n \leq 5000,ドル $\sum m \leq 500,000円$ |
| 4 | 17 | $\sum n \leq 500,000円,ドル $\sum m \leq 500,000円,ドル помимо других коридоров, есть коридоры, соединяющие комнаты $i$ и $i+1$ (1ドル \leq i \leq n - 1$), и комнаты $n$ и 1ドル$ |
| 5 | 12 | $\sum n \leq 500,000円,ドル $\sum m \leq 500,000円,ドル из каждой комнаты выходит не более 3ドル$ коридоров |
| 6 | 23 | $\sum n \leq 500,000円,ドル $\sum m \leq 500,000円$ |
4 4 4 1 2 2 3 3 4 4 1 5 5 1 2 2 3 3 4 4 5 5 1 5 6 1 2 3 2 1 3 3 5 5 4 3 4 9 12 1 2 2 3 3 1 4 5 5 6 6 4 7 8 8 9 9 7 3 6 6 9 9 3
-1 2 -1 4 2 2 4 2 2 4 4 2 2 6 6 4 6 6 4
В четвертом наборе входных данных погрузчик может выполнить следующие действия, чтобы из комнаты 1ドル$ с поднятой коробкой быстрее всего оказаться в комнате 4ドル$ с поднятой коробкой:
Всего будет потрачено 6ドル$ единиц времени.