【数据加强版】道路重建
题目描述
同 [P1272 重建道路](https://www.luogu.org/problemnew/show/P1272)
输入输出格式
输入格式
同 [P1272 重建道路](https://www.luogu.org/problemnew/show/P1272)
输出格式
同 [P1272 重建道路](https://www.luogu.org/problemnew/show/P1272)
输入输出样例
输入样例 #1
11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11输出样例 #1
2说明
$50\%$ 的数据，$1\le p\le n\le 1000$ 。
$100\%$ 的数据，$1\le p\le n\le 100000$，$n\times p\le 10^8$ 。