Егор — известный российский певец, рэпер, актёр и блогер, и наконец-то он решил дать концерт в солнечной республике Дагестан.
В республике есть \(n\) городов, некоторые пары которых соединены \(m\) односторонними дорогами без дополнительных условий. Иными словами, дорожная сеть Дагестана представляет собой произвольный ориентированный граф. Егор собирается прилететь в город \(1\), проехать из него по дорогам вдоль некоторого пути до города \(n\), дать в нём концерт и улететь.
Как и у любого артиста, у Егора есть множество недоброжелателей и слишком назойливых фанатов, поэтому ездить Егор и его команда будут только по безопасным дорогам. В Дагестане есть два типа дорог, чёрные и белые: по чёрным можно безопасно проехать только ночью, а по белым — только утром. Перед началом поездки менеджер Егора составляет расписание: он выбирает для каждого города его тип, чёрный или белый, и если команда посещает какой-то город, то уехать из него она сможет только по одной из дорог соответствующего типа. После определения расписания Егор выбирает любой маршрут из города \(1\) в город \(n\), причём из соображений безопасности этот путь должен быть кратчайшим. Менеджер Егора очень любит Дагестан и хочет задержаться здесь подольше, поэтому он попросил Вас составить такое расписание, чтобы из города \(1\) в город \(n\) не существовало пути вообще, или кратчайший путь был максимально возможной длины.
Путём является один город или последовательность дорог такая что начало каждой дороги в последовательности (кроме первой) является концом предыдущей. Егор может перемещаться вдоль пути, только если все его дороги безопасны.
Длиной пути называется количество дорог в нём. Кратчайшим путём называется путь минимальной длины.
Выходные данные
В первой строке выведите длину искомого пути (или \(-1\), если можно подобрать расписание так, чтобы пути из \(1\) в \(n\) не существовало).
Во второй строке выведите искомое расписание — строку из \(n\) целых чисел, где \(i\)-е число равно \(0\), если из \(i\)-го города можно уехать только по ночным дорогам, и \(1\), если только по утренним.
Если существует несколько решений, выведите любое из них.
Примечание
В первом примере, если покрасить город \(1\) в белый цвет, кратчайший путь будет состоять из одной дороги, \(1 \rightarrow 3\). Иначе, независимо от цветов остальных городов кратчайший путь будет \(1 \rightarrow 2 \rightarrow 3\).
Во втором примере город \(3\) следует покрасить в чёрный цвет, а из города \(2\) существуют дороги обоих цветов в город \(4\). Обратите внимание: может существовать дорога, соединяющая город с самим собой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
1 2 0
1 3 1
2 3 0
2 3 1
|
2
011
|
|
2
|
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
|
|
3
|
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
|