a278. TOI 2024/11 潛力組：鐵路

題目描述

N 座車站的編號為 0 到 N−1，M 條雙向軌道連接它們。能透過軌道互相到達的所有車站構成一個鐵路網。

鐵路公司要在每個鐵路網內保留足夠的軌道，使任意兩座不同車站之間恰好只有一條路徑；若原本有多餘軌道，就會將它停用，但不會把一個鐵路網拆開。

請分別計算有幾個鐵路網需要停用軌道，以及有幾個鐵路網完全不必停用軌道。

輸入格式

第一行輸入 N、M，2 ≤ N ≤ 1000，1 ≤ M ≤ N(N−1)/2。 接下來 M 行各有 A、B，表示兩座車站之間的雙向軌道，其中 0 ≤ A、B < N 且 A ≠ B。 任意兩站之間至多一條軌道，每座車站至少連接一條軌道。

輸出格式

輸出兩個整數，以空白隔開：先是需要停用軌道的鐵路網數，接著是不必停用任何軌道的鐵路網數。

來源

TOI 2024 年 11 月潛力組〈鐵路〉。依官方題意重新撰寫，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202411/Rail.pdf