require "matrix"

class Matrix
	def []=(i,j,x)
		@rows[i][j]=x
	end
end

def exp(n, k, mod = nil)
	x = 1	
	r = n
	while k > 0
		x *= r if k & 1 == 1
		r *= r		
		if mod
			x %= mod
			r %= mod
		end
		k >>= 1
	end
	x
end

class Matrix
	def %(dummy)
		map{|x| x.abs}
	end
end

loop {
	n, m, z = gets.split.map &:to_i
	break if n == 0

	edges = (1..m).map {
		e = gets.split.map &:to_i
		[e, e.reverse]
	}.flatten(1)

	mat = Matrix.zero(2*m)
	(0..2*m-1).each{|i|
		(0..2*m-1).each{|j|
			mat[i, j] = 1 if edges[i][1] == edges[j][0] && edges[i][0] != edges[j][1]
		}
	}

	u = Matrix.row_vector((0..2*m-1).map{|i| edges[i][0] == 1 ? 1 : 0})
	mat
	v = Matrix.column_vector((0..2*m-1).map{|i| edges[i][1] == n ? 1 : 0})
	p (u * (z > 1 ? exp(mat, z-1, 1) : 1) * v)[0, 0] > 0
}