ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Romanian Open Contest December 2001

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Pairs

Time limit: 1.0 second
Memory limit: 64 MB
A Romanian software company has bought N computers, which are going to be connected so that they may form a network. A connection can be made between any 2 distinct computers and is bidirectional (if the 2 computers are labeled i and j, then data can be sent both from i to j and from j to i). Your job is to determine a way to connect all the N computers, in such a way that every 2 computers will be able to send data between them (directly or using other computers as intermediate devices).
There is only one extra requirement: the network must contain exactly K critical pairs. A pair (i, j) is critical if there exists a connection which, if removed, data communication between i and j will become impossible.


The input consists of 2 integer numbers: N (1 ≤ N ≤ 100), the number of computers the network will contain and K (0 ≤ K ≤ N*(N-1)/2), the number of critical pairs the network will contain.


You should output the connections which form the network, one connection per line. A connection is described by a pair (i, j), which means that i and j are directly connected. The 2 numbers of the pair should be separated by a blank. If you cannot build a network which contains exactly K critical pairs, then you should output -1.


7 12
1 2
1 3
2 3
3 4
4 5
4 6
4 7
5 6
5 7
6 7
Problem Author: Mugurel Ionut Andreica
Problem Source: Romanian Open Contest, December 2001
To submit the solution for this problem go to the Problem set: 1169. Pairs