영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Arvid is preparing for the AI Olympiad final. There's much to do: arranging accommodations, organizing food, preparing problems, and setting up snacks for everyone. Stressed out, Arvid accidentally mixes up the last two tasks. As a participant in the AI Olympiad, you must solve the strange problem that arose.
A neural bakework is a directed graph with N nodes, designed to bake cookies. Initially, X units of ingredients are placed on node 1, while all other nodes start with zero ingredients. Every second, the following occurs simultaneously for all nodes:
- Let a_v be the number of ingredients on node v, and d_v be its out-degree.
- If d_v = 0, nothing happens. Otherwise, let a_v = d_v · q + r where 0 ≤ r < d_v. Afterwards send q units of ingredients to each node pointed to by v, and keep the remainder r.
In other words, each node splits its ingredients as evenly as possible and forwards the result. All updates happen simultaneously across all nodes each second, so the processing order of nodes does not matter.
The ingredients reaching node N become finished cookies. For the neural bakework to be valid, no node may point to itself, and no node may have multiple edges to the same target.
Given integers X and Y, your task is to construct a neural bakework that produces exactly Y cookies when X units of ingredients are used. Specifically, the bakework will run for 10^4 seconds, and if node N ends up with Y cookies, the test case is solved. Your score depends on minimizing N.
Input
The input consists of a single line with two integers X and Y (1 ≤ X, Y ≤ 10^18).
Output
If no valid neural bakework can produce Y cookies from X ingredients, output -1.
Otherwise, output first a line with two integers N and M, the number of nodes and edges in your network. Then output M lines, each containing two integers u_i, v_i (1 ≤ u_i, v_i ≤ N), representing an edge from node u_i to v_i.
Scoring
There are two test groups that scores independently. Each test group contains a set of test cases.
Let N_max be the maximum value of N in your solution across all test cases in a group. If N_max ≤ 30 then you get full points for the group, otherwise, points are calculated as:
(20 · g)/(N_max - 10)
where g is the group's total points (20 or 80).
If N_max ≥ 200 or your answer is incorrect for any test case, you get 0 points for the group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 20 | X, Y ≤ 20 |
| 2 | 80 | No additional constraints. |
예제
예제 1
15 4
8 10 1 2 2 3 3 4 4 2 1 4 1 5 5 6 5 7 6 8 7 8
예제 2
1 2
-1