Z-red TLE?

My solution goes TLE at every example, but works fine for all examples i test it.

Vlado, You use 9000 x 9000 matrix. This is 81 Mega what You use. For long 162 MB for long long 325 MB. It is allowed only 16 or 32 MB. This is reason for Your TLE.

O yeah, I forgot for memory limit. :) So i`ll need to do this with adjacency list insted of matrix?