(7 ĐIỂM) PHÁT QUÀNHÂN DỊP LỄ NOEN ÔNG GIÀ NOEN PHẢI MANG CÁC MÓN QUÀ...

Bài 6 : (7 điểm) Phát quà

Nhân dịp lễ Noen ông già Noen phải mang các món quà khác nhau có mã số từ 1..m để

tặng cho n em nhỏ mã số 1..n vui lễ Noen ở một làng quê. Trước khi phát quà, mỗi em nhỏ đã viết

ra giấy những món quà mà em đó mơ ước. Yêu cầu: Bạn hãy giúp ông già Noen chia các phần quà

sao cho mỗi em có đúng 1 phần quà mà em đó yêu thích.

Dữ liệu: vào từ file văn bản NOEN.INP

• Dòng 1: chứa hai số nguyên dương n và m (m  n).

• Dòng thứ i trong số n dòng tiếp theo: k b

b

.. b

– k là số lượng quà em i yêu thích; b

b

.. b

là mã số các món quà em i yêu thích.

Kết quả: Ghi ra file văn bản NOEN.OUT

• v – số em nhỏ đã nhận được quà.

• v dòng tiếp theo mỗi dòng 2 số i b cho biết em I được nhận món quà b

Ví dụ:

NOEN.INP NOEN.OUT Ý nghĩa: Có 4 em và 5 món quà: em 1 thích 3 món

quà 1, 2 và 5; : em 2 thích 1 món quà 5; : em 3 thích

4

4 5

1 1 2 5

3 1 2 5

2 món quà 1 và 4; : em 4 thích 3 món quà 2, 4 và 1.

1 5

 Phương án phát quà như sau:

2 1 4

3 4

11; 2  5; 3  4; 4  2

3 2 4 1

4 2