{"code":"upup","name":"Nâng Cấp Đường","description":"Hôm nay  [WuTan](https://lqdoj.edu.vn/user/WuTan)  phải đi khảo sát địa hình ở xứ sở KaHaLand nhằm mục đích nâng cấp, tu sửa hệ thống cầu đường ở đây.\r\n\r\nMạng lưới giao thông ở KaHaLand rất độc đáo, có dạng là một đồ thị cây gồm  $N$ nút giao thông, các nút giao thông đánh số từ  $1  đến  N$, giữa các nút giao thông có $N−1$  đường đi hai chiều, đảm bảo $2$ nút giao thông bất kỳ có thể đi đến được với nhau\r\n\r\nTrong thời gian làm việc,  [WuTan](https://lqdoj.edu.vn/user/WuTan)  nhận thấy người dân hằng ngày chỉ đi qua những tuyến đường cố định, cụ thể có  $M$ tuyến đường mà người dân sẽ đi qua nhiều nhất trong ngày, các tuyến đường này được đánh số từ $1  đến  M$, tuyến đường thứ $i$ xuất phát từ nút giao thông có số thứ tự $u[i]$ và kết thúc ở nút giao thông có số thứ tự  $v[i]$.\r\n\r\n[WuTan](https://lqdoj.edu.vn/user/WuTan)  cho rằng, việc đi lại giữa trong xứ sở KaHaLand sẽ trở nên khó khăn hơn nếu có nhiều tuyến đường đi có chung ít nhất 1 con đường. Nên chi phí để xây dựng sẽ được tính bằng  **số cặp tuyến đường có chung với nhau ít nhất 1 con đường**, hay nói cách khác là  **chung ít nhất 1 cạnh của đồ thị**.\r\n\r\nVì vậy để đảm bảo cho việc giao thông thuận lợi,  [WuTan](https://lqdoj.edu.vn/user/WuTan)  cần sửa chữa các tuyến đường này nhanh nhất có thể. Bạn cũng nằm trong đội ngũ khảo sát địa hình lần này của  [WuTan](https://lqdoj.edu.vn/user/WuTan)  hãy giúp anh ấy tính toán rủi và chi phí thật nhanh nhé!\r\n\r\n#### Input\r\n-   Dòng đầu gồm $2$  số nguyên dương  $N,M$  ($2 \\leq N,M \\leq 3.10^5$) lần lượt là số lượng nút giao thông và số lượng tuyến đường trọng yếu\r\n\r\n-  $N−1$ dòng tiếp theo, mỗi dòng gồm $2$ số $x$ và $y$ ($1\\leq x,y \\leq N,  x  \\neq  y$)  đại diện cho 1 con đường nối trực tiếp $2$ nút giao thông $x$  và  $y$.\r\n-  $M$  dòng tiếp theo, mỗi dòng gồm $2$  số  $u$  và  $v$  ($1 \\leq u,v \\leq N$, $u$ có thể bằng $v$) đại diện cho 1 tuyến đường trọng yếu xuất phát từ $u$ và kết thúc ở $v$.\r\n#### Output\r\n\r\n-   Gồm một số duy nhất là kết quả tìm được.\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n\t\t4 2\r\n\t\t1 2\r\n\t\t2 3\r\n\t\t3 4\r\n\t\t1 2\r\n\t\t1 4\r\n\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1\r\n        ```\r\n   \r\n!!! question \"Test 2\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n\t\t7 3\r\n\t\t1 2\r\n\t\t2 3\r\n\t\t2 4\r\n\t\t4 5\r\n\t\t5 6\r\n\t\t5 7\r\n\t\t4 5\r\n\t\t7 6\r\n\t\t2 6\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        2\r\n        ```\r\n       \r\n    ??? warning \"Note\"\r\n        Trong test ví dụ $2$: các cặp đó là\r\n        \r\n        -   cặp  **(1,3)** chung cạnh **(4,5)**\r\n        -  cặp **(2,3)** chung **(5,6)**","points":700.0,"partial":true,"time_limit":2.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}