Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NTPFECT - Đại diện hoàn hảo

Cho đồ thị G=(V,E) vô hướng liên thông không chu trình. Các đỉnh được đánh số từ 1 đến n. Tập hợp D được gọi là đại diện hoàn hảo của G nếu thỏa mãn:

  • D là tập con của V.
  • Với mỗi đỉnh u không thuộc D có đường nối trực tiếp từ u tới ít nhất 1 đỉnh trong D.
  • D chứa ít phần tử nhất.

Cho đồ thị G. Hãy xác định |D|.

Input

Gồm nhiều bộ dữ liệu, mỗi bộ dữ liệu cho trên 1 nhóm dòng.:

  • Dòng đầu tiên ghi n (1≤n≤1000)
  • n-1 dòng tiếp theo, mối dòng ghi 2 số u,v mô tả một cạnh của đồ thị

Dữ liệu kết thúc bằng dòng chứa một số 0.

Output

Trên mỗi dòng ghi ra kết quả tương ứng với từng bộ dữ liệu.

Example

Input:
6
1 3
2 3
3 4
4 5
4 6
2
1 2
0

Output:
2
1

Được gửi lên bởi:senga
Ngày:2010-01-05
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS PERL6 PYPY RUST SED

hide comments
2018-01-01 09:09:10
1/1/2018
ledacthuongvq
2017-12-04 08:15:46
nhật hào sạch
2017-12-03 10:58:36
bài hay
{dinh truong lam}
2017-08-11 16:05:29
1 dam AC
2016-12-25 10:01:57
Chú ý trường hợp Đa đồ thị là ez AC :))
2015-01-04 07:53:03 ■■‡[ND] Bee Sociu■■‡
O(n-1)
2015-01-03 14:03:00 Nắng
O(n)
2014-06-10 13:20:27 Hướng Thái Dương
nhiều test v~ trg
2013-11-07 16:43:50 a;slkfjasl;fkj


Last edit: 2013-11-07 16:46:41
2011-08-25 16:52:46 Noyethug
co' tat ca? bao nhiu test vay PS
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.