Ալգորիթմներ և Տվյալների Կառուցվածքներ

Գրաֆի լրացումը գտնել

Ձեզ տրված է մի չուղղորդված գրաֆ, որը բաղկացած է v գագաթներից և e կողերից։ Պահանջվում է գտնել այդ գրաֆի լրացումը։
Գրաֆի լրացումն այն գրաֆն է, որում կապեր (կողեր) կան հենց այն բոլոր զույգ գագաթների միջև, որոնց մեջ նախորդ գրաֆում կապ չկար, և հակառակը՝ չկա կապ այն գագաթների միջև, որոնք բնօրինակ գրաֆում կապված էին։
notion image

Մուտք

Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր v (1 ≤ v ≤ 500) և e (1 ≤ e ≤ 100 000)։
Следующиe e տողերում նշված են զույգեր v1, v2 (1 ≤ v1, v2 ≤ v), որոնք նշանակում են, որ v1 գագաթը կապված է v2 գագաթի հետ և հակառակը։

Ելք

Ծրագիրը պետք է տպի լրացուցիչ գրաֆի հարևանության ցուցակը (adjacency list)։ Յուրաքանչյուր տողի սկզբում պետք է գրված լինի տվյալ գագաթի համարը, այնուհետև (:)-ի նշանը, ապա այդ գագաթի բոլոր հարևանները։ Յուրաքանչյուր տողում հարևանների միջև բացատ է օգտագործվում որպես բաժանիչ։ Գագաթների և հարևանների ցանկի հերթականությունը կամայական է։

Օրինակներ

Մուտք
Ելք
4 4 1 2 4 2 4 1 3 4
1: 3 2: 3 3: 1 2 4:
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue