FROGPARTY - Frog Party

no tags 

In the local pond there are n lillypads arranged in a row - frog households - numbered 1 to n from left to right. One frog lives on each lillypad. In the afternoon, each frog returns to its household for a short nap. After they wake up from their naps, it is already evening. And what do frogs do on evenings? They throw a party! Luckily, a frog party doesn't require any special preparations - all the frogs simply meet up at a single lillypad, and the fun may begin.

When a frog goes to a party, it definitely doesn't want to arrive wet. Hence, frogs may only travel to the party by jumping across lillypads. A single frog by itself can jump to a neighbouring lillypad. However, when a frog jumps to a lillypad with another frog on it, they team up - the frog that arrived jumps on the other's back, and with combined efforts (and slightly defying the laws of physics) they can jump to a lillypad which is at a distance of 2. In general, if there are y frogs on the lillypad numbered x, they can jump to lillypads with numbers x-y and x+y (jumping outside the n lillypads is obviously forbidden - the frogs would jump into the water and get wet). When frogs from one lillypad jump onto another, they climb on the backs of the frogs which were already present, in the same order as before. On top of that, polite frog manners say that frogs should not jump on a lillypad on which there are currently no frogs.

The whole process might look like this

A frog party

As you can imagine, when several frogs stand on another's back, it can be quite tiring. Frog Michal obviously doesn't want to do activities which are tiring. That's why he would like to propose a sequence of jumps at the next frog meeting, such that in the evening all frogs will end up meeting on one lillypad, and at the same time no frog ever climbed on Michal's back (that basically means that no frog can ever jump to the lillypad on which Michal is currently situated). Help him!

Given the number of lillypads n and the number of lillypad on which Michal lives, produce a sequence of jumps so that all frogs end up on a single lillypad, and no frog ever jumps on a lillypad which currently has no frogs on it, or has frog Michal on it.


The first line contains an integer 1 ≤ T ≤ 60: the number of testcases.

For each testcase, in the only line of input there are two whole numbers n and m1 ≤ m ≤ n ≤ 106: the number of lillypads (and frogs), and the number of the lillypad on which Michal lives.

The sum of n within a single input file does not exceed 2*106.


For each testcase, if no valid sequence of jumps which fulfills the criteria described exists, output "NO". Otherwise in the first line output "YES", and then describe a valid sequence of jumps. Each jump can be described by two numbers 1 ≤ a,b ≤ n, meaning that the frogs currently on lillypad a should jump to the lillypad b. Any valid sequence of jumps leading to a frog party will be accepted.

The output is very large. Please be wary of your I/O speed.


5 4
9 3
2 3
3 5
4 5
5 1 
1 2
3 2
4 5
6 5
7 8
9 8
8 5
2 5

The first case is depicted in the images in the problem text.

hide comments
:D: 2019-10-20 20:24:39

Fun problem. Not that hard to figure out, but implementation details can be a little bit tricky.

Sushovan Sen: 2017-09-05 08:03:27

@Hodobox : Will you please tell me whether my solution is wrong or it is failing in some particular cases?

RE: it is very strange - your code gets AC when submitted in CPP14, CPP14-CLANG, and CPP, but gives WA with C++4.3.2. I'm really not sure what could cause that, Blue Mary got AC with C++4.3.2...

RE: Thank you for quick reply. Got AC. I will try to figure out why.

Last edit: 2017-09-05 13:30:46
mahilewets: 2017-08-28 19:45:49

At first I have misunderstood the statement

After implementing I have correctly understood the statement

So the problem is not easy (for me)

Giving up


Added by:Hodobox
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:Frog Jumping - Numberphile