Գրաֆի Տրանսպոնացումը

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

<figure>

Գրաֆի տրանսպոնացումը կարևոր է, երբ անհրաժեշտ է գտնել հակառակ ուղիները կամ գրաֆի մեջ առկա հակադարձ կապերը: Դասընթացում առաջիկայում կտեսնենք դրա կիրառման մի քանի օրինակ:

Մուտք

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

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

Ելք

Ծրագիրը պետք է տպի լրացուցիչ գրաֆի հարևանությունների ցուցակը: Յուրաքանչյուր տող պետք է սկսվի գագաթի համարով, որին անմիջապես հետևի दुईկետը (:), ապա նրա հարակից գագաթների ցանկը: Յուրաքանչյուր տողում հարակից գագաթների միջև պետք է դրվի բացատ (space): Թե՛ գագաթների, թե՛ դրանց հարակիցների հերթականությունը կամայական է:

Օրինակ