e-olymp
Задачи

Клика

Клика

Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней. Ваша задача – определить размер самой большой клики в графе.

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

Первая строка входного файла содержит одно число – количество тестов T. Далее следует T описаний тестов. Каждое описание теста начинается со строки, на которой расположены два целых числа N (1N20) и M (0MN(N-1)/2), где:

  • N – количество вершин графа,
  • M – количество рёбер графа.

Затем следует M строк, i-я строка содержит пару чисел (si, fi) – номера вершин графа, между которыми есть ребро (1si, fiN). Все пары (si, fi) различные, одно ребро не может быть во входных данных дважды. В графе нет кратных рёбер (любую пару вершин соединяет не более одного ребра). В графе нет элементарных циклов (для каждой пары (si, fi) верно, что sifi).

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

Для каждого из T тестов выведите в отдельной строке одно число – размер самой большой клики графа.

Лимит времени 25 секунд
Лимит использования памяти 64 MiB
Входные данные #1
3
2 0
2 1
1 2
3 2
1 2
2 3
Выходные данные #1
1
2
2