Գրաֆը դարձնել ամբողջական
Տրված է ոչ ուղղորդված գրաֆ, որն ունի
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 |
Բացատրություն
- Գագաթ 4-ն ի սկզբանե կապ չուներ գրաֆի որևէ այլ գագաթի հետ, ուստի այն պետք է կապենք գրաֆի բոլոր մյուս գագաթներին:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB