Bạn An có N người bạn. Hôm nay là sinh nhật An và đương nhiên, An muốn mời các bạn của mình đến nhà. Các bạn của An có tính cách rất lạ. Bạn X chỉ cảm thấy vui khi có ít nhất K người bạn khác là bạn của bạn X. Đương nhiên, An muốn các bạn đến dự sinh nhật của mình phải thật vui vẻ, không ai cảm thấy buồn.
Hãy giúp An chọn ra nhiều người bạn nhất để dự sinh nhật mà trong đó mỗi người bạn phải quen ít nhất K người bạn khác được đến dự sinh nhật.
Input
- Dòng đầu tiên gồm 3 số nguyên N, M, K (1 <= K <= N <= 10^5, M <= 10^5).
- M dòng tiếp theo, mỗi dòng gồm 2 số U, V, nghĩa là bạn U và bạn V quen nhau (U, V <= N)
Output:
- Dòng đầu ghi ra số bạn nhiều nhất tìm được.
- Dòng sau ghi ra chỉ số các bạn theo thứ tự tăng dần.
I
Input | Output |
5 5 2 1 2 2 3 1 3 3 4 4 5 |
3 1 2 3 |
Chỉ có 3 bạn được đi dự sinh nhật. Bạn 5 không được đi do chỉ quen 1 bạn là bạn 4. Nếu bạn 5 không đi thì bạn 4 cũng chỉ có một người bạn quen là bạn 3. Do vậy cả bạn 4 và bạn 5 đều không đi.