ТПУ: основной тур

Соревнование завершилось 15.04.18 в 16:00

D. Топология

Ограничение по времени: 1 с.
Ограничение по памяти: 256 МБ

Имеется прямоугольный рисунок из чёрных и белых пикселей, для которого выполняются такие правила:

  1. Только чёрные пиксели находятся на краю изображения.

  2. Разные области одного цвета не имеют точек касания.

Вот несколько примеров для лучшего понимания второго правила:

image

Рисунок а — правило не выполняется, чёрные области касаются друг друга в точках.

Рисунок б — правило не выполняется, внешняя и внутренняя белые области соприкасаются.

Рисунок в — правило выполняется, показанное может быть частью рисунка

Для этого рисунка Вам нужно построить дерево, которое показывает вложенность одноцветных областей. Если область A находится внутри области B и они касаются друг друга, то вершина A является дочерней для вершины B. Вершины имеют цвета соответствующих областей на изображении. Ниже приведён пример полного изображения и соответствующего ему дерева.

image

Входные данные

Первая строка входных данных содержит целые положительные числа n и m, разделённые одним пробелом — количество строк и столбцов на изображении (1 \leqslant n, m \leqslant 100).

Далее следуют n строк по m цифр. Единица означает, что соответствующий пиксель этой строки имеет чёрный цвет, ноль — белый.

Выходные данные

В первой строке требуется вывести одно целое число k — количество вершин в дереве.

В последующих k строках необходимо вывести описания вершин. i-я строка должна содержать описание i-й вершины в следующем формате:

Буква ‘w’, если вершина белая, или ‘b’, если она — чёрная, а затем номера всех вершин, являющихся дочерними для i-й. Буква отделяется от номеров вершин пробелом, номера вершин так же разделяются пробелами.

Номера дочерних вершин можно выводить в любом порядке. Если дочерних вершин нет, то описание i-й вершины состоит только из буквы, обозначающей её цвет.

Корневая вершина должна быть первой, остальные вершины могут быть пронумерованы в любом порядке. Нумерация должна быть непрерывной.

Примеры
Стандартный вводСтандартный вывод
5 7
1111111
1000001
1010101
1000001
1111111
4
b 2
w 3 4
b
b
5 7
1111111
1000101
1010111
1000101
1111111
5
b 2 3 4
w
w 5
w
b