Задача Кубики

Pascal ABC
Вообще не могу понять((

Родители подарили Пете набор детских кубиков. Поскольку Петя скоро пойдет в школу, они купили ему кубики с буквами. На каждой из шести граней каждого кубика написана буква.

Теперь Петя хочет похвастаться перед старшей сестрой, что научился читать. Для этого он хочет сложить из кубиков ее имя. Но это оказалось довольно сложно сделать - ведь разные буквы могут находиться на одном и том же кубике и тогда Петя не сможет использовать обе буквы в слове. Правда одна и та же буква может встречаться на разных кубиках. Помогите Пете!

Дан набор кубиков и имя сестры. Выясните, можно ли выложить ее имя с помощью этих кубиков и если да, то в каком порядке следует выложить кубики.
Входные данные

В первой строке вводится число N (1 <= N <= 100) - количество кубиков в наборе у Пети. Во второй строке задано имя Петиной сестры - слово, состоящие только из больших латинских букв, не длиннее 100 символов. Следующие N строк содержат по 6 букв (только большие латинские буквы), которые написаны на соответствующем кубике.
Выходные данные

В первой строке выведите "YES" если выложить имя Петиной сестры данными кубиками можно, "NO" в противном случае.

В случае положительного ответа, во второй строке выведите M различных чисел из диапазона 1…N, где M - количество букв в имени Петиной сестры. i-е число должно быть номером кубика, который следует положить на i-е место при составлении имени Петиной сестры. Кубики нумеруются с 1, в том порядке, в котором они заданы во входных данных. Если решений несколько, выведите любое. Разделяйте числа пробелами.

Добавлено через 14 минут
Находил такое решение, но как это реализовать на Pascal:

Эта задача сводится к нахождению максимального паросочетания в двудольном графе. Рассмотрим кубики и буквы имени сестры как вершины графа и соединим кубик ребром с буквой, если эта буква написана на этом кубике. Заметим, что граф действительно двудольный, а выбор кубиков для выкладывания имени эквивалентен построению паросочетания. Поскольку количество ребер в паросочетании не превышает количества вершин в меньшей доле, то искомое паросочетание действительно максимально.

Добавлено через 2 минуты
ПРИМЕРЫ:

Входные данные:
2
AB
AAAAAB
AAAAAA
Выходные данные

YES
2 1

Входные данные:
3
ANNY
AAAAAA
NNNNNN
YYYYYY

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

NO

0

Сообщение от volshebnik88 ПРИМЕРЫ: ... Входные данные: 3 ANNY

гениальный пример. Дано три кубика и слово из 4-х букв. Можно ли этими тремя кубиками выложить четырёхбуквенное слово? Загадка, прямо!

теперь по поводу решения задачи.
Тот текст, что ты привёл насчёт двудольного графа - это в точку! Но я, например, тоже не соображу, как это можно применить.

знаешь, как я бы решал эту задачу?
я бы завёл булевую матрицу 100 x 26
столбцы - это буквы латинского алфавита
строки - это номера кубиков.
в I-й строке и J-m столбце 1 (true) ставим, если на кубике с номером I есть J-я буква
получаем матрицу
например, для первого примера
дальше сложнее. нужно на матрице найти строки, которые имеют 1 в нужных столбцах (AB)
очевидно, что если мы выберем 1 для буквы A, то не останется ни одной строки, где B равна 1
если выберем строку 2 для буквы A, то для буквы B останется строчка 1
поэтому ответ 2 1

Возможно, что то, что я пишу бред и тут нужно просто использовать какой-нибудь известный алгоритм поиска в графе.
но я, к сожалению, в теории графов не силён.

1

Про создании матрицы я тоже думал, но вот , как дальше быть? Сложно. Как реализовать этот поиск? А еще , что для меня самое сложное, это вывести номера кубиков.

0