Задача №114766. Тяжелый груз
Операторам склада необходимо переместить тяжелую коробку с использованием специального погрузчика. Склад можно схематически представить как \(n\) комнат, соединенных \(m\) коридорами. От любой комнаты можно добраться до любой другой, перемещаясь по коридорам. Комнаты пронумерованы от \(1\) до \(n\). Коридор номер \(i\) непосредственно соединяет комнаты с номерами \(u_i\) и \(v_i\), по коридору можно перемещаться в обоих направлениях.
Погрузчик может поднимать и опускать коробку, а также, если он не держит коробку, перемещаться по свободным комнатам и коридорам. Изначально погрузчик находится в комнате номер \(1\), и держит поднятую коробку. Погрузчику доступны следующие действия:
- Если погрузчик находится в комнате \(a\) и держит поднятую коробку, он может, не сдвигаясь с места, поставить коробку в комнату \(b\), если комнаты \(a\) и \(b\) непосредственно соединены коридором. После этого действия погрузчик не держит коробку и может перемещаться.
- Если погрузчик находится в комнате \(a\), а коробка стоит в комнате \(b\), и комнаты \(a\) и \(b\) непосредственно соединены коридором, погрузчик может, не перемещаясь, поднять коробку. После этого действия погрузчик остается в комнате \(a\) и держит поднятую коробку, он не может перемещаться, пока не поставит коробку.
- Если погрузчик не держит коробку, он может перемещаться по коридорам и комнатам, однако он не может проходить через комнату, где лежит коробка.
Пустой погрузчик перемещается между комнатами очень быстро, гораздо быстрее, чем он поднимает или опускает коробку. Поэтому будем считать, что на выполнение первого или второго действия погрузчик тратит одну единицу времени, а третье действие выполняется мгновенно. Ваша задача — для каждой комнаты \(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\).
| Ограничения | ||||||
| Подз. | Баллы | \(\sum n\) | \(\sum m\) | дополнительно | Необх. подзадачи | Информация о проверке |
| 1 | 16 | \(\sum n \leq 1000\) | \(\sum m \leq 2000\) | У | первая ошибка | |
| 2 | 18 | \(\sum n \leq 1000\) | \(\sum m \leq 100\,000\) | У, 1 | первая ошибка | |
| 3 | 14 | \(\sum n \leq 5000\) | \(\sum m \leq 500\,000\) | У, 1–2 | первая ошибка | |
| 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\) | У, 1–5 | первая ошибка | |
В четвертом наборе входных данных погрузчик может выполнить следующие действия, чтобы из комнаты \(1\) с поднятой коробкой быстрее всего оказаться в комнате \(4\) с поднятой коробкой:
- Поставить коробку в комнату \(2\). Тратится одна единица времени.
- Переместиться в комнату \(3\). Время не тратится.
- Поднять коробку из комнаты \(2\). Тратится одна единица времени.
- Поставить коробку в комнату \(9\). Тратится одна единица времени.
- Переместиться в комнату \(6\). Время не тратится.
- Поднять коробку из комнаты \(9\). Тратится одна единица времени.
- Поставить коробку в комнату \(5\). Тратится одна единица времени.
- Переместиться в комнату \(4\). Время не тратится.
- Поднять коробку из комнаты \(5\). Тратится одна единица времени.
Всего будет потрачено \(6\) единиц времени.
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