HỘ N Ị QUỐC TẾ (4 ĐIỂM) RO ỘT Ộ Ị QUỐC TẾ CÓ ĐẠ...

Bài 4. Hộ n ị quốc tế (4 điểm)

ro ột ộ ị quốc tế có đạ ểu t dự được đá số từ 1 đế . ạ ộ ị có sử

dụ ô ữ k ác u được đá số từ 1 đế . Mỗ đạ ểu ết ột số ô ữ tro ô ữ

đó. H đạ ểu u v v có t ể tr o đổ vớ u ếu ết ột ô ữ c u oặc các đạ ểu k ác

p ê dịc .

K ột đạ ểu u uố chào đạ ểu v, đạ ểu u sẽ ó to c o ằ ột ô ữ đạ

ểu ết v các đạ ểu ết ô ữ đều ểu được c o này. ếu đạ ểu v k ô ểu

c o đó (v k ô ết ô ữ i), có ột số đạ ểu k ác p ê dịc tru để đạ ểu v ểu được

c o từ đạ ểu u. Gọ uv số đạ ểu có t ể ểu được c o củ đạ ểu u d c o đạ ểu v.

Yêu cầu: Vớ ỗ cặp u, v (1≤ u ≤ , 1 ≤ v ≤ ) , xác đị số dươ a uv ỏ ất.

Dữ l ệu v o từ tệp BAI4.INP:

- Dò đầu c ứ số u ê dươ v , 2 ≤ ≤ 300, 1 ≤ ≤ 300.

- Trong m dòng t ếp t eo, dò t ứ (1 ≤ ≤ ) c ứ số u ê dươ k i số ượ các ô ữ

đạ ểu t ứ ết, t ếp t eo k i là số ệu các ô ữ đó t eo t ứ tự tă , 1 ≤ k i ≤ .

Kết quả r v o tệp BAI4.OUT: Gồ dò và cột. ạ vị trí dò t ứ u, cột t ứ v số uv tìm

được, 1≤ u ≤ , 1 ≤ v ≤ . ro đó _uu = 0. ếu đạ ểu u v v k ô t ể ểu c o củ nhau thì

a uv = -1.

Ví dụ:

BAI4.INP BAI4.OUT G ả t ích

0 2 3 3

4 3

- Đạ ểu 1 ử c o tớ đạ ểu 2 ằ các sử dụ ô

ữ 1 có 2 đạ ểu ểu c o 1 v 2.

2 0 2 4

2 1 3

2 1 2

3 2 0 3

2 2 3

3 4 3 0

ữ 3. S u đó đạ ểu 3 c u ể c o s ô ữ 2 để đạ

1 3

ểu 2 ểu được. Có 4 đạ ểu ểu c o là 1, 2, 3 và 4.

ừ đó 12 = a 21 = 2.

Lưu ý: 50% số test ứ vớ 50% số đ ể củ có 2 ≤ ≤ 100, 1 ≤ ≤ 100.