Задача « Новая Вавилония »
На острове Новая Вавилония каждый житель владеет несколькими языками. Любые два жителя А и В могут вести между собой беседу только в двух случаях: если они оба владеют каким-нибудь общим для них языком, или с помощью нескольких жителей-переводчиков П1, П2,..., П^. Последнее означает, что любую фразу жителя А переводчик П1 сможет перевести так, что его поймет П2, житель П2 сможет перевести эту фразу на другом языке жителю П3 и так далее, наконец, переводчик П*. сможет общаться с и В. Вам нужно определить наименьшее количество переводчиков, которое необходимо для того, чтобы жители А и В могли поговорить друг с другом.
Формат входного файла input.txt Первая строка содержит одно число N (2 < N< 1000) - количество жителей на острове. В каждой /-ой из N последующих строк записаны: число /., (1 < /.,< N) - количество языков, которыми владеет /'-ый житель, а затем, через пробел, /., различных целых чисел, не превосходящих N, - номера этих языков. (На острове все языки пронумерованы целыми числами от 1 до N.) В последней (N + 2)-ой строке записаны через пробел номера жителей А и В - различные натуральные числа, не превосходящие N.
Формат выходного файла output.txt Выходной файл содержит два разделенных пробелом задуманных числа. Выведите -1, если беседа жителей А и В невозможна. Выведите 0, если А и В владеют общим языком, то есть им переводчики не нужны. В противном случае в первой строке запишите единственное натуральное К - наименьшее количество переводчиков, необходимое для поддержания беседы жителей А и В. Во второй строке укажите через пробел номера жителей-переводчиков П1; П2,..., П^, которые обеспечивают разговор между А и В. Если возможных решений несколько, выведите любое из них.
| INPUT.TXT |
| 2
1 1 1 2 1 2 |
| OUTPUT.TXT |
| -1 |
| INPUT.TXT |
| 2
1 1 1 1 1 2 |
| OUTPUT.TXT |
| 0 |