Yeddi Segmentli Ekran
Yeddi seqmentli rəqəmli göstəricilər hər yerdə geniş istifadə olunur. Bu göstəricilər rəqəmləri göstərmək üçün yeddi seqmentdən ibarətdir.
Aşağıda tipik bir yeddi seqmentli göstəricidə istifadə olunan bütün seqmentləri təsvir edən bir şəkil verilmişdir (bundan sonra rahatlıq üçün SSD qısaltmasından istifadə edəcəyik).
Şəkil 1: SSD təmsilatı üçün istifadə olunan seqmentlər.
Burada, DP onluq nöqtəni təmsil edir, lakin bu problemin kontekstində bu zəruri deyil.
Aşağıda isə 0-dan 9-a qədər olan rəqəmlərin SSD-də təmsil olunması göstərilmişdir.
0 seqmentlərdən istifadə edir A, B, C, D, E, F
1: B, C
2: A, B, G, E, D
3: A, B, C, D, G
4: B, C, F, G
5: A, C, D, F, G
6: A, C, D, E, F, G
7: A, B, C
8: A, B, C, D, E, F, G
9: A, B, C, D, F, G
İndi, bir rəqəmin SSD təmsilatını qraf kimi təsəvvür edin. Seqmentlərin ucları düyünlərdir və seqmentlər kənarlardır. Beləliklə, rəqəmlər belə görünəcək:
Bu təmsilata 0-dərəcəli SSD qrafı deyirik. k-dərəcəli (k > 0) SSD qrafı, 0-dərəcəli qrafın hər bir kənarını k+1 kənara bölməklə və aralarına k düyün əlavə etməklə yaradılır.
Daha çox izah etmək üçün, bütün rəqəmlərin 1-dərəcəli qrafları aşağıda göstərilmişdir. Tünd rəngli düyünlər yeni əlavə edilmiş düyünlərdir.
Sizə n düyün və m kənar ilə bir qraf veriləcək. Verilən qraf üçün uyğun olan bütün (dərəcə, rəqəm) cütlərini çap etməlisiniz.
Giriş verilənləri
Girişin ilk sətri test halları sayını göstərən bir tam ədəd T (1 ≤ T ≤ 20) ehtiva edir. T dəst halları izləyəcək. Hər bir hal n (1 ≤ n ≤ 500) və m (1 ≤ m ≤ 1000) - düyünlərin sayı və kənarların sayı ilə başlayacaq. Növbəti m sətrin hər biri bir cüt ədəd (u, v) ehtiva edəcək ki, bu da düyün u-dan düyün v-yə bir kənar olduğunu bildirir. Düyünlər 1-dən n-ə qədər nömrələnir. Girişdə təkrarlanan və ya öz-özünə kənarlar olmadığına zəmanət verilir.
Çıxış verilənləri
Hər bir giriş dəsti üçün bir çıxış dəsti verin. Bir dəstin ilk sətri, Case X: Y formatında olmalıdır (burada, X girişin sıra nömrəsi və Y isə (rəqəm, dərəcə) cütlərinin sayıdır) bir sətirdə. Sonra hər bir (rəqəm, dərəcə) cütünü çap edin - hər cütü bir sətirdə. Cütlər əvvəlcə rəqəmə, sonra dərəcəyə görə sıralanmalıdır. Cütdəki hər bir rəqəm bir boşluq ilə ayrılmalıdır. Ardıcıl test halları arasında bir boş sətir çap edin.