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?
Constraints
Subtask 1 [50%]
Subtask 2 [50%]
No additional constraints.
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.
Comments