Flusso massimo#11163
Il fermiere John ha installato un nuovo sistema di n - 1 tubi per trasportare il latte tra stalle nel suo fienile, comodamente numerate da a . Ogni tubo collega una coppia di stalle, e tra due stalle qualsiasi esiste un unico percorso attraverso i tubi.
FJ pompa il latte tra coppie di stalle. Per l'-esima di queste coppie, vi vengono dati due stalle, s_i e t_i, che sono gli estremi del percorso lungo il quale il latte viene pompato a una velocità di un'unità per unità di tempo. FJ è preoccupato che alcune stalle possano risultare sovraccariche a causa dell'elevata quantità di latte che le attraversa, poiché una singola stalla può fungere da punto intermedio in molti dei percorsi lungo i quali viene pompato il latte.
Aiutatelo a determinare la quantità massima di latte che attraversa una qualsiasi stalla. Se il latte viene pompato lungo un percorso da s_i a t_i, si considera che attraversi entrambe le stalle terminali, s_i e t_i, così come ogni stalla situata tra di esse lungo tale percorso.
Nella prima riga si trovano due numeri interi n~(2 \le n \le 50000) e k~(1 \le k \le 10^5).
Nelle successive n - 1 righe, ciascuna contiene due numeri interi, e y~(x \ne y), che descrivono un tubo che collega le stalle e .
Nelle successive righe, ciascuna contiene due numeri interi, e , che indicano le stalle terminali di un percorso lungo il quale viene pompato il latte.
Stampate un numero intero che indichi la quantità massima di latte che attraversa una qualsiasi stalla nel fienile.
Esempio 1