Liên lạc


Submit solution

Points: 2.5
Time limit: 1.0s
Memory limit: 977M

Author:
Problem type

Một lớp gồm \(N\) học sinh, mỗi học sinh cho biết những bạn mà học sinh đó có thể liên lạc được (chú ý liên lạc này là liên lạc hai chiều: \(u\) có thể gửi tin tới \(v\) và \(v\) cũng có thể gửi tin tới \(u\)).

Thầy Tích đang cần thông báo lịch kiểm tra và lịch thi tới tất cả các học sinh. Để tiết kiệm thời gian, thầy chỉ nhắn tin tới một số học sinh mà thầy tin cậy nhất rồi sau đó nhờ các học sinh này nhắn lại cho tất cả các bạn mà các học sinh đó có thể liên lạc được, và cứ lần lượt như thế làm sao cho tất cả các học sinh trong lớp đều nhận được tin.

Hãy tìm một số ít nhất các học sinh mà thầy Tích cần nhắn tin và liệt kê những bạn mà thầy đã liên lạc.

Đầu vào

Dòng đầu gồm hai số nguyên \(N\) và \(M\) lần lượt là số lượng học sinh và số lượng liên lạc hai chiều. \((2 \le N \le 1000, 0 \le M \le N*(N-1)/2)\)

Dòng thứ hai gồm \(N\) số nguyên dương phân biệt \(t[i]\) là độ tin cậy của học sinh thứ \(i\). \((1 \le t[i] \le 10^5, 1 \le i \le N)\)

\(M\) dòng tiếp theo, mỗi dòng gồm hai số \(u, v\) cho biết học sinh \(u\) có thể liên lạc tới học sinh \(v\) và ngược lại.

Đầu ra

Dòng thứ nhất là số học sinh tối thiếu mà thầy Tích cần nhắn tin.

Dòng thứ hai là những học sinh thầy đã liên lạc. (In ra theo thứ tự tăng dần và cách nhau bởi dấu cách)

Ví dụ

Đầu vào

5 4
90 85 100 75 65
1 2
1 3
2 3
4 5

Đầu ra

2
3 4

Giải thích

Học sinh \(1, 2, 3\) có thể liên lạc cho nhau nhưng \(3\) có độ tin tưởng cao nhất \((100)\) nên chọn \(3\).

Học sinh \(4, 5\) có thể liên lạc cho nhau nhưng \(4\) có độ tin tưởng lớn hơn \((75)\) nên chọn \(4\).


Comments

There are no comments at the moment.