Вам дан связный, неориентированный и невзвешенный граф с \(n\) вершинами и \(m\) рёбрами. Обратите внимание на ограничение на количество рёбер: \(m \le n + 2\).
Давайте скажем, что мы красим некоторые рёбра в красный и оставшиеся рёбра в синий. Теперь рассмотрим только красные рёбра и посчитаем количество компонент связности в графе. Пусть это значение равно \(c_1\). Аналогично, рассмотрим только синие рёбра и посчитаем количество компонент связности в графе. Пусть это значение равно \(c_2\).
Найдите распределение цветов по рёбрам такое, что величина \(c_1+c_2\) минимальна.
Выходные данные
Для каждого набора входных данных выведите бинарную строку длины \(m\). \(i\)-й символ строки должен быть 1, если \(i\)-е ребро должно иметь красный цвет, и 0, если оно должно иметь синий цвет. Если существует несколько способов распределить цвета, чтобы получить минимальную величину, вы можете вывести любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 7
1 2
2 3
3 4
4 5
5 1
1 3
3 5
4 4
1 2
2 3
1 4
3 4
6 7
1 2
1 3
3 4
4 5
1 4
5 6
6 2
2 1
1 2
|
0111010
1001
0001111
0
|