COVID

Điểm số: 1

Giới hạn thời gian: 2s

Giới hạn bộ nhớ: 512 MB

Người đăng: admin

Hải đang làm việc tại một tập đoàn đa quốc gia có n nhân viên được đánh mã số thứ tự từ 1 đến n. Mỗi người có một phòng làm việc riêng của mình. Do nhu cầu công việc, hàng ngày mỗi nhân viên có thể phải tiếp xúc với một số nhân viên khác. Vào một ngày đẹp trời, Hải bị nhiễm Covid, nhưng do không biết nên Hải vẫn đi làm. Đến cuối ngày người ta mới phát hiện ra Hải là người nhiễm Covid đầu tiên, Khả năng lây lan của Covid rất nhanh chóng, một người nhiễm bệnh nếu tiếp xúc với một người khác có thể sẽ truyền bệnh cho người này, chính vì thế hiện tại thế giới đã có hơn 63 triệu người nhiễm bệnh.

Hãy giúp các bác sĩ kiểm tra xem cuối ngày hôm đó, có tối đa bao nhiêu người có thể sẽ nhiễm bệnh và đó là những người nào để còn cách ly. Người có tiếp xúc với người nhiễm bệnh được coi là người nhiễm bệnh.

Đầu vào:

  • Dòng đầu tiên ghi 2 số tự nhiên n,k (1<=n<=10^5, 1<=k<=n) tương ứng là số lượng người làm việc trong toà nhà và mã số của nhân viên đã nhiễm Covid đầu tiên.
  • Dòng thứ i trong n dòng tiếp theo ghi danh sách những người có tiếp xúc với người thứ i theo cách sau: số đầu tiên m của dòng là tổng số nhân viên đã gặp người thứ i, tiếp theo là m số tự nhiên lần lượt là số hiệu của các nhân viên đó. Nếu m=0 có nghĩa rằng i không tiếp xúc với ai.
  • Dữ liệu được cho đảm bảo tổng số lần tiếp xúc của tất cả nhân viên trong cơ quan không vượt quá 10^6

Đầu ra:

  • Dòng đầu tiên ghi số s là tổng số người có thể bị lây nhiễm Covid
  • Dòng thứ 2 liệt kê tất cả nhân viên có thể bị lây nhiễm Covid cần cách ly, danh sách cần được sắp theo thứ tự tăng dần của số hiệu nhân viên.

 

Ví dụ:

Đầu vào

Đầu ra

5 1
2 2 3
2 1 3
2 1 2
1 5
1 4

3
1 2 3