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

Գրաֆը դարձնել ամբողջական

Տրված է ոչ ուղղորդված գրաֆ, որն ունի v գագաթ և e կող: Ձեզ խնդրում են գտնել բոլոր այն կողերը, որոնք անհրաժեշտ է ավելացնել, որպեսզի գրաֆը դառնա ամբողջական:

Մուտք

Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր v (1 ≤ v ≤ 500) և e (1 ≤ e ≤ ):

Հաջորդ e տողերում յուրաքանչյուր տող դրական երկու ամբողջ թվեր v1, v2 (1 ≤ v1, v2 ≤ v) են, որոնք ներկայացնում են կող v1 և v2 գագաթների միջև:

Ելք

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

Օրինակներ

Մուտք

Ելք

4 3
1 2
2 3
3 1

1 4
2 4
3 4

Բացատրություն

  1. Գագաթ 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