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

Условие

Двудольным графом называется граф (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

Problem D. 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

Задача E. Прямые ≡

Условие

Даны n прямых на плоскости. Ваша задача — выбрать максимально возможное подмножество этих прямых так, чтобы среди выбранных прямых не было одинаковых прямых, параллельных прямых, прямых имеющих один и тот же y пересечения с прямой x = 0.

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

На первой строке количество тестов T, далее идёт описание T тестов. Первая строка теста содержит количество прямых n. Каждая из следующих n строк содержит по три целых числа A_i, B_i и C_i, описывающих прямую, как множество точек (x, y), для которых A_i x + B_i y + C_i = 0. Сумма n по всем тестам не превосходит 3000.

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

Для каждого теста на одной строке выведите k — максимальный размер подмножества прямых. На следующей строке k целых чисел от 1 до n — номера выбранных прямых в произвольном порядке. Прямые нумеруются от 1 в том порядке, в котором даны в описании теста. Если существует несколько оптимальных решений, выведите любое одно.

Ограничения

1 ≤ n ≤ 3000

 − 10⁹ ≤ A, B, C ≤ 10⁹, A² + B² > 0

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

2
2
1 1 0
1 1 1
2
-1 1 1
-2 1 1

1
1
1
1

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

Условие

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

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

В первой строке файла даны два числа 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

Задача G. Мошенники ≡

Условие

Студенты придумали N тем для курсовых, название каждой состоит из двух слов из заглавных букв английского алфавита. Среди студентов есть читеры, которые вместо того, чтобы придумывать собственные названия, взяли оба слова из уже придуманных их коллегами тем. При этом в качестве первого слова они взяли первое слово одной из тем, а в качестве второго второе. Вам даны все N названий в произвольном порядке, определите максимальное число читеров среди студентов.

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

Первая строка содержит число тестов T. Каждый тест содержит N и N пар слов — названия тем. Все названия различны.

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

Выведите максимальное число читеров. Формат вывода смотрите в примере.

Ограничения

1 ≤ T ≤ 100, 1 ≤ N ≤ 1000, длины слов от 1 до 20.

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

3
3
HYDROCARBON COMBUSTION
QUAIL BEHAVIOR
QUAIL COMBUSTION
3
CODE JAM
SPACE JAM
PEARL JAM
2
INTERGALACTIC PLANETARY
PLANETARY INTERGALACTIC

Case #1: 1
Case #2: 0
Case #3: 0