Програмчлал, Алгоритмд дуртай бүхэнд зориулав

N ширхэг нүдний ямар нэгэн хоёр нүдэнд муур хулгана тус тус байрлаж байжээ. Эдгээр нүднүүдийн зарим нь хоорондоо холбоостой бөгөөд нэг ээлжинд эхлээд хулгана дараа нь муур холбоост нүднүүдэд дамжин хөөцөлдөж байв. Хулгана аль болох удаан зугтах, муур аль болох хурдан барих төлөвлөгөөтэй байв. Тийм бол хэдэн ээлж болоход муур хулганыг барьж чадах вэ?

Оролт
Эхний мөр T тестийн тоо /0< Т < = 100/
Дараагийн мөрөнд эхний тестийн нүдний тоо N, /1 < N < = 50/
Тэгээд холбоосийг илэрхийлэх N*N матриц /зай болон мөрөөр тусгаарласан, 1 бол холбоост, 0 бол холбоосгүй/
Тэгээд хулганы байрлаж байгаа нүдний дугаар муурын байрлаж байгаа нүдний дугаар өгөгдөнө. /0-ээс эхлэж дугаарлана/
Дараагын тест
....

Гаралт
Тест болгоны хувьд харгалзах хариуг нэг нэг мөрөнд, хэрвээ муур хулганыг барьж чадахгүй бол "infinity" гэж хэвлэ.

Жишээ оролт
2
8
0 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0
0 1 0 1 1 0 0 0
0 0 1 0 0 0 0 0
0 0 1 0 0 1 1 0
0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 1
0 0 0 0 0 0 1 0
3 0
4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
3 0

Жишээ гаралт
5
infinity