Codeforces Round 669 (Div. 2) |
---|
Закончено |
Егор — известный российский певец, рэпер, актёр и блогер, и наконец-то он решил дать концерт в солнечной республике Дагестан.
В республике есть $$$n$$$ городов, некоторые пары которых соединены $$$m$$$ односторонними дорогами без дополнительных условий. Иными словами, дорожная сеть Дагестана представляет собой произвольный ориентированный граф. Егор собирается прилететь в город $$$1$$$, проехать из него по дорогам вдоль некоторого пути до города $$$n$$$, дать в нём концерт и улететь.
Как и у любого артиста, у Егора есть множество недоброжелателей и слишком назойливых фанатов, поэтому ездить Егор и его команда будут только по безопасным дорогам. В Дагестане есть два типа дорог, чёрные и белые: по чёрным можно безопасно проехать только ночью, а по белым — только утром. Перед началом поездки менеджер Егора составляет расписание: он выбирает для каждого города его тип, чёрный или белый, и если команда посещает какой-то город, то уехать из него она сможет только по одной из дорог соответствующего типа. После определения расписания Егор выбирает любой маршрут из города $$$1$$$ в город $$$n$$$, причём из соображений безопасности этот путь должен быть кратчайшим. Менеджер Егора очень любит Дагестан и хочет задержаться здесь подольше, поэтому он попросил Вас составить такое расписание, чтобы из города $$$1$$$ в город $$$n$$$ не существовало пути вообще, или кратчайший путь был максимально возможной длины.
Путём является один город или последовательность дорог такая что начало каждой дороги в последовательности (кроме первой) является концом предыдущей. Егор может перемещаться вдоль пути, только если все его дороги безопасны.
Длиной пути называется количество дорог в нём. Кратчайшим путём называется путь минимальной длины.
Первая строка содержит числа $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 500000$$$, $$$0 \leq m \leq 500000$$$) — количество городов и дорог, соответственно.
В $$$i$$$-й из следующих $$$m$$$ строк даны три целых числа — $$$u_i$$$, $$$v_i$$$ и $$$t_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$t_i \in \{0, 1\}$$$) — номера городов, соединяемых дорогой, и тип дороги ($$$0$$$ — ночная, $$$1$$$ — утренняя).
В первой строке выведите длину искомого пути (или $$$-1$$$, если можно подобрать расписание так, чтобы пути из $$$1$$$ в $$$n$$$ не существовало).
Во второй строке выведите искомое расписание — строку из $$$n$$$ целых чисел, где $$$i$$$-е число равно $$$0$$$, если из $$$i$$$-го города можно уехать только по ночным дорогам, и $$$1$$$, если только по утренним.
Если существует несколько решений, выведите любое из них.
3 4 1 2 0 1 3 1 2 3 0 2 3 1
2 011
4 8 1 1 0 1 3 0 1 3 1 3 2 0 2 1 0 3 4 1 2 4 0 2 4 1
3 1101
5 10 1 2 0 1 3 1 1 4 0 2 3 0 2 3 1 2 5 0 3 4 0 3 4 1 4 2 1 4 5 0
-1 11111
В первом примере, если покрасить город $$$1$$$ в белый цвет, кратчайший путь будет состоять из одной дороги, $$$1 \rightarrow 3$$$. Иначе, независимо от цветов остальных городов кратчайший путь будет $$$1 \rightarrow 2 \rightarrow 3$$$.
Во втором примере город $$$3$$$ следует покрасить в чёрный цвет, а из города $$$2$$$ существуют дороги обоих цветов в город $$$4$$$. Обратите внимание: может существовать дорога, соединяющая город с самим собой.
Название |
---|