Задача . F. Два различных

Вам дано целое число \(n\).

Вы должны найти список пар \((x_1, y_1)\), \((x_2, y_2)\), ..., \((x_q, y_q)\) (\(1 \leq x_i, y_i \leq n\)) который удовлетворяет следующему условию.

Рассмотрим некоторую функцию \(f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) (мы определяем \(\mathbb{N}\) как множество положительных целых чисел). Другими словами, \(f\) это функция, возвращающая положительное целое число по паре положительных целых чисел.

Давайте рассмотрим массив \(a_1, a_2, \ldots, a_n\), где изначально \(a_i = i\).

Вы сделаете \(q\) операций, в \(i\)-й из них вы сделаете:

1. присвоите \(t = f(a_{x_i}, a_{y_i})\) (\(t\) это временная переменная, она используется только для следующих двух присвоений);
2. присвоите \(a_{x_i} = t\);
3. присвоите \(a_{y_i} = t\).

Другими словами, вам нужно одновременно заменить \(a_{x_i}\) и \(a_{y_i}\) на \(f(a_{x_i}, a_{y_i})\). Обратите внимание, что в течение процесса значение \(f(p, q)\) всегда одинаково для заданных положительных целых чисел \(p\) и \(q\).

В конце должно быть не больше двух различных чисел в массиве \(a\).

Это должно быть выполнено для любой функции \(f\).

Найдите любой возможный список пар. Количество пар должно не превосходить \(5 \cdot 10^5\).