Problem A. Bipartite graph ≡

Statement

For a given undirected graph with N vertices and M edges you need to figure out whether the graph is bipartite or no.

NOTE. A graph is called bipartite if it's possible to split its vertices into two non-empty sets so that there is no edges between any two vertices from the same set.

Input file format

Output file format

Constraints

Sample tests

3 2
1 2  1 3

BIPARTITE

4 6
1 2  2 3  3 4  4 1  1 3  2 4

NO

Задача B. Паросочетание ≡

Условие

Двудольным графом называется граф (V,E), E ⊂ V × V такой, что его множество вершин V можно разбить на два подмножества A и B, для которых ∀ (e₁,e₂) ∈ E e₁ ∈ A, e₂ ∈ B и A, B ⊂ E, A ∩ B = varnothing.

Паросочетанием в двудольном графе называется любой его набор несмежных ребер, то есть такой набор S ⊂ E, что для любых двух ребер e₁ = (u₁, v₁), e₂ = (u₂, v₂) из S выполнено u₁ ≠ u₂ и v₁ ≠ v₂.

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

Формат входного файла

В первой строке записаны два целых числа n и m (1≤ n, m ≤ 250)  — число вершин в A и число вершин в B.

Далее следуют n строк с описаниями ребер. i-я вершина из A описана в i+1-й строке файла. Каждая из этих строк содержит номера вершин из B, соединенных с i-й вершиной A. Вершины в A и B нумеруются независимо (с единицы). Список завершается числом 0.

Формат выходного файла

Первая строка выходного файла должна содержать одно целое число l — количество ребер в максимальном паросочетании. Далее должны следовать l строк, в каждой из которых должны быть два целых числа u_j и v_j — концы ребер паросочетания в A и B, соотвественно.

Ограничения

Примеры тестов

2 2
1 2 0
2 0

2
1 1
2 2

Задача C. Слово из кубиков ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS

2 5 3 4

Задача D. Минимальное контролирующее множество ≡

Условие

Требуется построить в двудольном графе минимальное контролирующее множество, если дано максимальное паросочетание.

Формат входного файла

В первой строке файла даны два числа m и n (1≤ m, n≤ 4 000) — размеры долей. Каждая из следующих m строк содержит список ребер, выходящих из соответствующей вершины первой доли. Этот список начинается с числа K_i (0≤ K_i≤ n) — количества ребер, после которого записаны вершины второй доли, соединенные с данной вершиной первой доли, в произвольном порядке. Сумма всех K_i во входном файле не превосходит 500 000.

Последняя строка файла содержит некоторое максимальное паросочетание в этом графе — m чисел 0≤ L_i≤ n — соответствующая i-й вершине первой доли вершина второй доли, или 0, если i-я вершина первой доли не входит в паросочетание.

Формат выходного файла

Первая строка содержит размер минимального контролирующего множества.

Вторая строка содержит количество вершин первой доли S, после которого записаны S чисел — номера вершин первой доли, входящих в контролирующее множество, в возрастающем порядке.

Третья строка содержит описание вершин второй доли в аналогичном формате.

Ограничения

Примеры тестов

3 2
2 1 2
1 2
1 2
1 2 0

2
1 1
1 2