#P6717. [2019山东省队集训第一轮]chemistry

[2019山东省队集训第一轮]chemistry

[2019山东省队集训第一轮]Chemistry

题目描述

有 nn 个水杯,编号为 1,2,…,n1,2,\ldots,n,初始时每个杯子中都有 11 升水。

每次可以选择两个不同的杯子 i,ji,j。设它们当前分别有 x,yx,y 升水,要求 x≥yx\ge y。将杯子 ii 中的 yy 升水倒入杯子 jj,使两杯的水量分别变为

x−y,2y.x-y,\qquad 2y.

请在不超过 3n3n 次操作内,使编号为 11 的杯子恰有 kk 升水。其余杯子的最终水量没有要求。

若存在多种合法方案,输出任意一种即可;若无解,输出 −1-1。

输入格式

输入一行两个正整数 n,kn,k。

输出格式

若无解,仅输出一行 −1-1。

否则,第一行输出一个整数 mm,表示操作次数,须满足 0≤m≤3n0\le m\le3n。

接下来 mm 行,每行两个不同的整数 i,ji,j,表示从杯子 ii 向杯子 jj 倒水,使杯子 jj 的水量变为原来的两倍。每次操作前,杯子 ii 的水量必须不小于杯子 jj 的水量。

样例输入

5 3

样例输出

4
2 1
4 3
3 1
1 5

样例解释

五个杯子的水量依次变为:

$$\begin{aligned} &(1,1,1,1,1),\\ &(2,0,1,1,1),\\ &(2,0,2,0,1),\\ &(4,0,0,0,1),\\ &(3,0,0,0,2). \end{aligned}$$

最终第一个杯子有 33 升水。

数据范围

所有数据满足 1≤k≤n≤1051\le k\le n\le10^5。

  • 10%10\% 的数据满足 n≤10n\le10。
  • 40%40\% 的数据满足 1≤2k≤n≤1051\le2k\le n\le10^5。