| Когнитивные технологии. Финал 2024 |
|---|
| Finished |
Разработчик задач Олег устроился в Сбер. Ему поручили придумать новую задачу для тестирования стажеров. Он придумал совершенно новую и оригинальную задачу. В этой задаче участнику нужно посчитать в связном графе количество точек сочленения и мостов. Олег придумал красивую легенду, написал решение, однако забыл придумать тесты.
Связный граф — это граф, в котором существует путь между любой парой вершин.
Мост в связном графе — это ребро, удаление которого приводит к тому, что найдутся две вершины между которыми нет пути.
Точка сочленения в связном графе — это вершина, удаление которой приводит к тому, что найдутся две вершины между которыми нет пути.
Уже завтра олимпиада, поэтому Олег считает(из своего опыта), что одного теста в задаче достаточно. Олег хочет, чтобы в единственном тесте был задан связный граф ровно с $$$k_1$$$ мостами и $$$k_2$$$ точками сочленения. Помогите Олегу.
Можно показать, что в указанных ограничениях решение всегда существует.
В единственной строке даны два числа $$$k_1$$$ и $$$k_2$$$ ($$$1 \le k_1, k_2 \le 1000$$$) — количество мостов и точек сочленения в графе.
В первой строке выведите два числа $$$n$$$, $$$m$$$ ($$$3 \le n, m \le 10000$$$) — количество вершин и ребер в графе.
В следующих $$$m$$$ строках выведите по два целых числа $$$v_j, u_j$$$ ($$$1 \le v_j, u_j \le n$$$) — концы $$$j$$$-го ребра в графе.
Граф не должен содержать петель и кратных ребер.
3 2
4 3 1 2 2 3 3 4
Граф в примере. Рёбра между вершинами $$$1$$$—$$$2$$$, $$$2$$$—$$$3$$$, $$$3$$$—$$$4$$$ являются мостами, а вершины $$$2$$$, $$$3$$$ — точками сочленения.
Разработчик задачи не Олег. В задаче больше одного теста.
