Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Grafų saugojimo būdai

Duotas besvoris neorientuotas grafas. Parašykite programą, kuri išspausdintų duotą grafą pasitelkiant gretimumo matricą bei gretimumo sąrašus.

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai n ir m - grafo viršūnių ir briaunų kiekiai (1\\leqn\\leq1000,0\\leqm\\leq10^5).

Toliau pateikta m eilučių. i-ojoje iš jų pateikti du sveikieji skaičiai u_i ir v_i reiškiantys, kad grafe yra briauna tarp viršūnių u_i ir v_i.

Pradiniai duomenys tokie, kad juose nebus dvigubų briaunų ir kilpų.

Rezultatai

Iš pradžių programa turi išspausdinti duoto grafo gretimumo matricą. Ją turi sudaryti n eilučių, o kiekvienoje eilutėje turi būti po n simbolių. Jei tarp viršūnių i ir j yra briauna, tai i-osios eilutės j-asis simbolis turi būti 1, o kitu atveju - 0.

Toliau turi būti išspausdinta viena eilutė su lygiai vienu brūkšneliu (-).

Toliau turi būti išvesti grafo gretimumo sąrašai - n eilučių. i-oji iš šių eilučių prasideda skaičiumi k, nurodančiu, kiek kaimynių turi i-oji viršūnė. Toliau turi sekti k tarpais atskirtų sveikųjų skaičių - viršūnės, kurios yra i-osios viršūnės kaimynės. Viršūnės turi būti pateiktos didėjimo tvarka.

Kad būtų lengviau suprasti rezultatų formatą, panagrinėkite žemiau pateiktus pavyzdžius.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
6 10
1 3
1 5
1 6
2 4
2 5
2 6
3 4
3 5
4 6
5 6
 
001011
000111
100110
011001
111001
110110
-
3 3 5 6
3 4 5 6
3 1 4 5
3 2 3 6
4 1 2 3 6
4 1 2 4 5
 
8 7
2 4
3 2
4 3
5 7
7 8
2 6
5 8
 
00000000
00110100
01010000
01100000
00000011
01000000
00001001
00001010
-
0
3 3 4 6
2 2 4
2 2 3
2 7 8
1 2
2 5 8
2 5 7
 
6 6
3 1
3 2
3 4
3 5
3 6
5 4
 
001000
001000
110111
001010
001100
001000
-
1 3
1 3
5 1 2 4 5 6
2 3 5
2 3 4
1 3