Problem
Anda diberi pokok (graf tak berarah akiklik bersambung) yang terdiri daripada n bucu.
Cari saiz padanan maksimumnya (set tepi bukan bersebelahan berpasangan).
Input:
Baris pertama mengandungi nombor n - bilangan bucu dalam pokok.
Seterusnya ialah baris n-1, setiap satunya mengandungi dua nombor a
i dan b
i (1 <= a
i, b
i <= n) - tepi pokok.
Output:
Cetak satu nombor - saiz padanan maksimum pokok yang diberikan.
Contoh:
| Input |
Output |
4
1 2
23
3 4 |
2 |
Penjelasan:
Padanan maksimum pokok ini akan termasuk tepi 1-2 dan 3-4.