Կողի հեռացում
Տրված է
N գագաթ և M կող ունեցող կշռված, պարզ(*), կապակցված, ոչ ուղղորդված գրաֆ G։ Գագաթները համարակալված են 1-ից N հաջորդական ամբողջ թվերով, կողերը՝ 1-ից M հաջորդական ամբողջ թվերով։ i-րդ կողը միացնում է X ենթագրաֆի համար W(X)-ով նշանակենք X-ում ընկած կողերի կշիռների գումարը։Ձեր խնդիրն է ջնջել գրաֆից մի կող այնպես, որ առաջացած
A և B կապակցված կոմպոնենտների համար (եթե գրաֆը մնում է կապակցված, ապա համարել, որ B = Ø, W(Ø) = 0) |W(A) – W(B)| արտահայտության արժեքը լինի նվազագույնը։Եթե պայմանին բավարարող կողերը շատ են, ընտրել այն մեկը, որի դեպքում
(*) Հիշեցում՝ պարզ է կոչվում այն գրաֆը, որը չունի կրկնվող կողեր և գագաթը ինքն իրեն միացնող կողեր։
Մուտքային տվյալներ
Առաջին տողում տրված են
N և M ամբողջ թվերը։ Հաջորդ M տողերից յուրաքանչյուրը նկարագրում է գրաֆի մի կող՝ Ելքային տվյալներ
Հարկավոր է արտածել երկու թիվ՝ կողի գագաթների համարները։
Օրինակ
Մուտք | Ելք |
10 11
1 2 1
2 3 10
1 5 2
3 4 7
3 5 9
5 6 8
6 7 5
6 8 3
7 8 12
7 9 1
9 10 8 | 5 6 |
Աղբյուրը. Հանրապետական 2019
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB