P4757 [CERC2014] Parades

In The City of Eternal Festivities, there are $n$ street junctions and $n-1$ bidirectional streets,each street connecting two of the junctions. Between every two junctions, there is exactly one (direct or indirect) path connecting them. No junction is an endpoint for more than 10 streets. Every 13th of September (the 256th day of the year), there are many festivities going on in The City. In particular, the citizens want to organize $m$ parades. The parade number $i$ starts at junction $u_i$ and ends at $v_i$, following the unique path between the endpoints. As the mayor of The City, you are responsible for citizens’ safety. Therefore you decreed that no two parades are ever allowed to use the same street, though they can have common junctions,or even common endpoints. To appease your citizens, try to organize as many parades as possible, without breaking the safety regulations.

无

无