Во Крушево, постојат N споменици кои се поврзани со (N-1) двонасочни пешачки патеки, така што постои точно еден начин да се стигне од кој било споменик до кој било друг споменик. Кај два од овие споменици, се изградени хотели. За останатите (N-2) споменици, можеме да дефинираме мерка “изолираност”, како бројот на пешачки патеки кои треба да се поминат за да се стигне до поблискиот хотел (од двата кои постојат). Нормално, за двата споменика до кои има хотел, изолираноста е еднаква на 0.

На пример, за сликата дадена погоре каде што хотелите се до спомениците 1 и 2, кога се патува од споменикот 1 до споменикот 7, потребно е да се помине низ две патеки.

Нека дефинираме дека опасноста на едно патување (помеѓу два споменика) е еднаква на најмалата изолираност на некој споменик на тој пат. На пример, за сликата дадена погоре, опасноста на патувањето помеѓу 1 и 7 е еднаква на 0 (бидејќи најмалата изолираност на споменик на тој пат е на споменикот 1 која е еднаква на 0), помеѓу 4 и 7 е еднаква на 0 (пак, поради споменикот 1 чија изолираност е еднаква на 0), опасноста на патувањето помеѓу 3 и 10 е еднаква на 1, помеѓу 6 и 8 е еднаква на 1, помеѓу 7 и 8 е еднаква на 2, итн.

Со цел анализирање на моментната состојба на спомениците и пешачките патеки, напишете програма која ќе го пресмета збирот на опасностите на патувањата помеѓу сите парови споменици. На пример, доколку има три споменици, потребно е да се отпечати збирот на опасностите на патувањата помеѓу спомениците 1-2, 1-3, и 2-3.

Влез

Во првиот ред е запишан еден цел број N (2 <= N <= 100000), кој го означува бројот на споменици. Во секој од следните (N-1) редови е даден по еден пар споменици Xi и Yi (1 <= Xi, Yi <= N), кој означува дека постои пешачка патека помеѓу споменикот означен со реден број Xi и споменикот означен со реден број Yi. Хотелите се наоѓаат веднаш до спомениците означени со редните броеви 1 и 2.

Забелешка: Во тест случаи кои носат најмалку 10% од поените, бројот на споменици ќе биде N <= 50.
Во други тест случаи кои носат најмалку 10% од поените, бројот на споменици ќе биде N <= 1000.
За дополнителни 10% од поените, за сите патеки ќе важи Yi=Xi+1.

Излез

Отпечатете го бараниот збир од опасности.

Ограничувања

Временско ограничување: 200 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
10
4 1
9 1
1 6
6 7
7 8
2 5
3 10
2 3
6 2

излез
5

Објаснување: погледнете ја сликата. Конкретно, опасноста на патувањето помеѓу спомениците 6 и 7 е еднаква на 1, помеѓу спомениците 6 и 8 е еднаква на 1, помеѓу спомениците 7 и 8 е еднаква на 2, и опасноста на патувањето помеѓу спомениците 3 и 10 е еднаква на 1. Помеѓу сите други парови на споменици (на пример, 4 и 9, 3 и 4, 1 и 5, итн), опасноста на патувањето е еднаква на 0. Збирот е еднаков на 1+1+2+1=5.