C. Гольф
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Батыр придумал как играть в гольф на ориентированном графе. Но для этого нужен игровой ориентированный граф.

Назовем ориентированный граф игровым, если:

  1. Граф состоит хотя бы из $$$3$$$ вершин, где первая и вторая вершина являются конечными, и из них не исходят никакие ребра.
  2. Из всех вершин, кроме конечных исходят ровно по два ребра (оба ребра могут вести в одну и ту же вершину).
  3. Из каждой вершины в графе существует путь хотя бы в одну из конечных.

На игровом ориентированном графе Батыр выбирает стартовую вершину, отличающуюся от конечных вершин, в которую он положит мяч. Теперь Батыр начинает бить по мячу, пока он не попадет в одну из конечных вершин. Так как Батыр плохо играет, он бьет по мячу так, что он равновероятно пройдёт по одному из двух исходящих рёбер и попадёт в вершину куда ведет это ребро. что он равновероятно попадает в одну из двух вершин куда ведут ребра из этой вершины.

Постройте игровой ориентированный граф, состоящий из не более чем $$$n$$$ вершин, и выберите в ней стартовую вершину, что вероятность попасть в конечные вершины равна $$$\frac{a}{a+b}$$$ для первой конечной вершины и $$$\frac{b}{a+b}$$$ для второй.

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

Каждый тест содержит несколько наборов входных данных.

Первая строка содержит два целых числа $$$t$$$, $$$n$$$ $$$(1\le t \le 100, 33 \le n \le 100)$$$ — количество наборов входных данных и максимальное количество вершин для каждого набора.

Первая и единственная строка каждого набора входных данных содержит два целых числа $$$a$$$, $$$b$$$ $$$(1\le a, b \le 10^9)$$$.

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

Для каждого набора входных данных выведите граф в следующем формате.

В первой строке два целых числа $$$m, s$$$ $$$(3 \le m \le n, 3 \le s \le m)$$$ - количество вершин и стартовая вершина в графе.

В следующих $$$m - 2$$$ строках выведите по два числа $$$v_i, u_i$$$ $$$( 3 \le i \le m, 1 \le v_i, u_i \le m)$$$ - конечные вершины ребер исходящих из вершины $$$i$$$.

Вероятность попасть в вершину $$$1$$$, начиная с $$$s$$$, должна быть $$$\frac{a}{a+b}$$$.

Вероятность попасть в вершину $$$2$$$, начиная с $$$s$$$, должна быть $$$\frac{b}{a+b}$$$.

Также в этом графе из каждой вершины должен быть путь до хотя бы одной конечной.

Система оценки

Данная задача содержит $$$10$$$ подзадач.

Подзадача$$$n$$$Дополнительные ограниченияБаллыНеобходимые подзадачи
$$$0$$$—Примеры$$$0$$$—
$$$1$$$$$$100$$$$$$a+b=4$$$$$$10$$$—
$$$2$$$$$$100$$$$$$a+b=32$$$$$$10$$$—
$$$3$$$$$$50$$$$$$a+b=2^{30}$$$$$$10$$$—
$$$4$$$$$$33$$$$$$a,b\le15$$$$$$10$$$—
$$$5$$$$$$64$$$—$$$10$$$—
$$$6$$$$$$50$$$—$$$10$$$$$$5$$$
$$$7$$$$$$36$$$—$$$10$$$$$$6$$$
$$$8$$$$$$35$$$—$$$10$$$$$$7$$$
$$$9$$$$$$34$$$—$$$10$$$$$$8$$$
$$$10$$$$$$33$$$—$$$10$$$$$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$9$$$
Пример
Входные данные
4 100
1 1
1 2
1 3
2 3
Выходные данные
3 3
1 2
4 3
2 4
1 3
4 3
4 2
1 2
5 3
4 5
1 5
2 3