## Yet Another Contest 6 P1 - No More Separation

View as PDF

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

Nils is about to give a presentation about the impact of social media on the increasingly connected world. To help prove his point, he wants to fake construct a social network of people, who are labelled from to .

The network should contain pairs of people who are friends. The degree of separation between person and person is the smallest positive integer such that there exists a sequence of integers where:

• Person and person are friends, for all

• .

If no such sequence of integers exists, then the degree of separation is infinity.

Can you help Nils construct any network which minimises the sum of the degree of separation between all pairs of people?

#### Input Specification

The only line contains two space-separated integers, and .

#### Output specification

Print lines. The -th line should contain two different space-separated integers, representing the people involved in the -th friendship. No friendship should be listed twice.

If there are multiple valid answers, you may output any of them.

#### Sample Input

4 4

#### Sample Output

1 2
2 3
3 4
1 3

#### Explanation

In this social network, there are pairs of people with a degree of separation of , and pairs of people with a degree of separation of . Hence, the sum of all degrees of separation is , which is optimal.