Գրաֆի Տրանսպոնացումը
Տրված է ուղղորդված գրաֆ, որ ունի
v գագաթ և e կող: Ձեզ խնդրում են գտնել դրա տրանսպոնացված տարբերակը: Ուղղորդված գրաֆի տրանսպոնացումը ստացվում է, երբ գրաֆի բոլոր կողերի ուղղությունը շրջվում է: Այլ կերպ ասած, այն գրաֆ է, որտեղ նախնական գրաֆի մեջ եղած բոլոր ուղղորդված կողերը հայտնվում են հակառակ ուղղությամբ:<figure>
Գրաֆի տրանսպոնացումը կարևոր է, երբ անհրաժեշտ է գտնել հակառակ ուղիները կամ գրաֆի մեջ առկա հակադարձ կապերը: Դասընթացում առաջիկայում կտեսնենք դրա կիրառման մի քանի օրինակ:
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր
v (1 ≤ v ≤ 100 000) և e (1 ≤ e ≤ 100 000):Հաջորդ
e տողերից յուրաքանչյուրում տրված են երկու ամբողջ թվեր v1, v2 (1 ≤ v1, v2 ≤ v), որոնք սահմանում են, որ v1 գագաթից ուղղորդված կող կա դեպի v2 գագաթը:Ելք
Ծրագիրը պետք է տպի լրացուցիչ գրաֆի հարևանությունների ցուցակը: Յուրաքանչյուր տող պետք է սկսվի գագաթի համարով, որին անմիջապես հետևի दुईկետը (
:), ապա նրա հարակից գագաթների ցանկը: Յուրաքանչյուր տողում հարակից գագաթների միջև պետք է դրվի բացատ (space): Թե՛ գագաթների, թե՛ դրանց հարակիցների հերթականությունը կամայական է:Օրինակ
Մուտք | Ելք |
4 4
1 2
1 4
2 4
3 4 | 1:
2: 1
3:
4: 1 2 3 |
Constraints
Time limit: 3.5 seconds
Memory limit: 512 MB
Output limit: 1 MB