Задан взвешенный планарный граф ($$$^{\text{∗}}$$$) из $$$n$$$ вершин и $$$m$$$ рёбер.
Вам требуется найти в нём два множества: множество $$$T$$$ треугольников ($$$^{\text{†}}$$$) и множество $$$S$$$ рёбер такие, что:
$$$^{\text{∗}}$$$Планарный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам.
$$$^{\text{†}}$$$Треугольником является тройка вершин, каждые две из которых соединены ребром
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1023$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка набора входных данных содержит два целых числа $$$n$$$, $$$m$$$ ($$$2 \le n \le 300\,000$$$, $$$0 \le m \le 3n-6$$$) — число вершин и рёбер в графе соответственно. Вершины пронумерованы целыми числами от $$$1$$$ до $$$n$$$, рёбра пронумерованы целыми числами от $$$1$$$ до $$$m$$$.
Следующие $$$m$$$ строк содержат описание рёбер, $$$i$$$-я из них содержит три целых числа $$$a_i$$$, $$$b_i$$$, $$$w_i$$$ ($$$1 \le a_i \lt b_i \le n$$$, $$$1 \le w_i \le 10^9$$$), означающих, что $$$i$$$-е ребро соединяет вершину $$$a_i$$$ с вершиной $$$b_i$$$ и имеет вес $$$w_i$$$.
Гарантируется, что граф является планарным, а также не содержит петель и кратных рёбер.
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$300\,000$$$.
Для каждого набора входных данных выведите целые неотрицательные числа $$$s$$$ и $$$t$$$ — размеры $$$S$$$ и $$$T$$$ соответственно.
В $$$i$$$-й из последующих $$$s$$$ строк выведите числа $$$x_{i, 1}, x_{i, 2}$$$ ($$$1 \le x_{i,1}, x_{i,2} \le n$$$) — концы $$$i$$$-го из рёбер множества $$$S$$$.
В $$$j$$$-й из последующих $$$t$$$ строк выведите числа $$$y_{j, 1}, y_{j, 2}, y_{j, 3}$$$ ($$$1 \le y_{j, 1}, y_{j, 2}, y_{j, 3} \le n$$$) — вершины, входящие в $$$j$$$-й из треугольников множества $$$T$$$.
Рёбра $$$S$$$ и треугольники $$$T$$$, а также концы рёбер и вершины треугольников можно выводить в любом порядке.
23 31 2 11 3 12 3 14 61 2 11 3 11 4 12 3 12 4 13 4 1
2 12 33 11 2 32 11 24 31 4 3
| Algo Cup 2025 by csspace.io (Финал) |
|---|
| Закончено |
