{{ self.title() }}

{{ s('description') }}

有 $n$ 个非负整数，初始时为 $1, 2, \ldots, n$，你可以进行若干次以下操作：

• 选取其中的两个非负整数，设为 $x, y$ ($x \leq y$)，删去 $x$ 和 $y$，然后加入 $y - x$ 和 $x + y$。

你的目标是让所有数相等。设 $S$ 为所有这样的 (非负) 整数 $r$ 的集合，使得存在一组方案，使得最终所有数等于 $r$。请求出 $S$ 的最小值，并给出达到它的一组方案。

{{ s('input format') }}

{{ self.input_file() }}

输入共一行，包含一个正整数 $n$。

{{ s('output format') }}

{{ self.output_file() }}

如果 $S = \varnothing$，输出一行 $-1$。

否则，第一行包含两个非负整数 $r, m$ ($0 \leq m \leq 5 \times 10^5$)，表示 $S$ 的最小值和操作的次数。

接下来 $m$ 行，每行包含两个非负整数 $x, y$ ($0 \leq x \leq y$)，描述一次操作的两个整数。你需要保证此时 $x, y$ 为 $n$ 个整数中的两个。

{{ s('sample', 1) }}

{{ self.sample_text() }}

{{ self.title_sample_description() }}

$\left[ 1, 2, 3, 4 \right] \to \left[ 2, 2, 4, 4 \right] \to \left[ 0, 4, 4, 4 \right] \to \left[ 4, 4, 4, 4 \right]$。

{{ s('数据范围与提示') }}

对于所有的测试点，保证 $1 \leq n \leq 10^5$。

具体的测试点的数据规模见下表：

{{ tbl('constraints', width = [0.25, 0.25, 0.25]) }}