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 ~N~ people, who are labelled from ~1~ to ~N~.

The network should contain ~M~ pairs of people who are friends. The degree of separation between person ~X~ and person ~Y~ is the smallest positive integer ~k~ such that there exists a sequence of integers ~a_1, a_2, \dots, a_{k+1}~ where:

• ~a_1 = X~

• Person ~a_i~ and person ~a_{i+1}~ are friends, for all ~1 \le i \le k~.

• ~a_{k+1} = Y~

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

~2 \le N \le 5000~

~N-1 \le M \le \min(\frac{N(N-1)}{2}, 10^5)~

Subtask 1 [50%]

~M = N-1~

Subtask 2 [50%]

No additional constraints.

Input Specification

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

Output Specification

Print ~M~ lines. The ~i~-th line should contain two different space-separated integers, representing the people involved in the ~i~-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 ~4~ pairs of people with a degree of separation of ~1~, and ~2~ pairs of people with a degree of separation of ~2~. Hence, the sum of all degrees of separation is ~4 \times 1 + 2 \times 2 = 8~, which is optimal.