Cele N
noduri ale unui graf neorientat sunt numerotate cu numere intregi de la 1
la N. Gradul unui nod X
al grafului este egal cu numarul de muchii care au una dintre cele doua extremitati
in X. Un graf neorientat se numeste
K-regulat daca gradul fiecarui
nod este egal cu K. Un graf neorientat
se numeste conex daca se poate ajunge de la orice nod la oricare alt nod mergand
numai pe muchiile grafului.
Cerinta
Dandu-se K
si N, construiti un graf neorientat,
conex si K-regulat.
Date de intrare
Fisierul de intrare kreg.in
contine pe prima linie numerele intregi K
si N, separate printr-un spatiu.
Date de iesire
Fisierul de iesire kreg.out
va contine N*K/2 linii. Fiecare
linie corespunde unei muchii a grafului construit si va contine doua numere
intregi A si B,
separate printr-un spatiu, reprezentand extremitatile muchiei (1<=A,B<=N
, A diferit de B).
Restrictii si precizari
2<=K<=50,
K par
K+1<=N<=10000
In general, exista multe
grafuri K-regulate conexe.
Puteti determina oricare dintre ele. Muchiile grafului pot fi afisate in orice
ordine.
Exemplu
kreg.in
kreg.out
(o solutie posibila)
4 6
1 2
1 6
5 4
6 3
5 1
2 5
5 3
2 6
3 4
4 1
6 4
2 3
Mugurel Ionut Andreica
Universitatea Politehnica Bucuresti, Facultatea de Automatica si Calculatoare mugurel_ionut@yahoo.com