XẾP HẠNG CÓ HỌC SINH, ĐÁNH SỐ THỨ TỰ 1, 2, … , , THAM GIA MỘ...

Bài 2. Xếp hạng

Có học sinh, đánh số thứ tự 1, 2, … , , tham gia một cuộc thi lập trình. Các thí sinh được chấm

bài ngay trong thời gian thi nên mỗi bạn đều biết điểm thi của mình. Ban tổ chức cho biết không có

hai thí sinh nào có cùng điểm thi. Tuy nhiên, bảng xếp hạng cuối cùng lại chưa được công bố.

Rất mong muốn biết được thứ hạng để xác định “màu huy chương”, một số thí sinh đã so sánh điểm

thi với nhau. Có tất cả so sánh như vậy, kết quả mỗi so sánh là một cặp số nguyên ( ; ) được

hiểu là thí sinh có điểm cao hơn thí sinh , đồng nghĩa sẽ có thứ hạng kết quả cao hơn .

Cho biết thông tin về các lần so sánh, hãy xác định xem có bao nhiêu thí sinh đã có thể biết chính

xác thứ hạng của mình.

Dữ liệu (brank.inp)

• Dòng1: hai số nguyên , (1 ≤ ≤ 100; 1 ≤ ≤ 4500)

• Dòng2 … + 1: mỗi dòng là thông tin về một so sánh gồm hai số nguyên , (1 ≤

, ≤ ; ≠ ) chỉ thí sinh sẽ có thứ hạng cao hơn thí sinh . Các so sánh không mâu

thuẫn.

1/2

Kết quả (brank.out)

• Dòng 1: số nguyên là số lượng thí sinh có thể xác định chính xác thứ hạng kết quả.

Ví dụ

brank.inp brank.out giải thích

5 5

2 Hai thí sinh có thể biết chính xác thứ hạng là thí

4 3

sinh #2 và thí sinh #5

4 2

3 2

1 2

2 5