Графы

[pupkin152]

Дан ориентированный мультиграф. По его вершинам и рёбрам перемещаются фишки. Две фишки не
могут одновременно находиться на одном ребре или в одной вершине. Фишка перемещается по
графу из вершины в ребро, выходящее из этой вершины; либо из ребра в вершину, в которую входит
данное ребро. Изначально все фишки находятся в вершинах. Дано некое второе расположение
фишек, все фишки также в вершинах. Требуется определить, возможен ли на данном графе переход
фишек из первого положения во второе.
Формат ввода:
• в первой строке записано число вершин графа (n).
• в следующих строках дана матрица смежности A, каждое число aij в которой указывает,
сколько ребер выходит из i в j вершину. 1 <= i <= n. 1 <= j <= n. i – номер строки, j – номер
столбца.
• в следующей строке указано количество фишек m.
• в следующей строке перечислены номера вершин bi (1 <= i <= m), в которых изначально
располагаются фишки.
• в следующей строке указаны номера вершин в целевом расположении фишек в том же
формате.
В качестве вывода программы ожидается: True – если возможен переход фишек, False – если
переход фишек невозможен.
Примеры:
1.
Входная строка
2
0 1
1 0
2
1 2
2 1
Результат
True
2.
Входная строка
3
0 0 0
2 0 1
0 1 0
3
1 2 3
3 1 2
Результат
False