class BitMatrix
	def initialize(m, n)
		@rows = [0] * m
		@cols = [0] * n
	end

	def [](i,j)
		@rows[i][j]
	end

	def []=(i,j,x)
		raise "set non-binary value to BitMatrix" if x != 0 && x != 1
		@rows[i] |= (x << j)
		@cols[j] |= (x << i)
	end

	def row(i)
		@rows[i]
	end

	def col(i)
		@cols[i]
	end

	def row_size
		@rows.size
	end

	def col_size
		@cols.size
	end

	def *(other)
		return self.dup if other == 1

		prod = self.class.new(self.row_size, other.col_size)
		(0..prod.row_size-1).each{|i|
			(0..prod.col_size-1).each{|j|
				prod[i, j] = self.row(i) & other.col(j) > 0 ? 1 : 0
			}
		}
		prod
	end

	def to_s
		@rows.map{|b|
			s = b.to_s(2)
			s.reverse + "0" * (@rows.size - s.size)
		}.join("\n")
	end
		
end

def exp(n, k, mod = nil)
	x = 1
	r = n
	while k > 0
		x = r * x if k & 1 == 1
		r *= r		
		if mod
			x %= mod
			r %= mod
		end
		k >>= 1
	end
	x
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 = BitMatrix.new(2*m, 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 = BitMatrix.new(1, 2*m)
	(0..2*m-1).each{|i|
		u[0, i] = 1 if edges[i][0] == 1 
	}
	v = BitMatrix.new(2*m, 1)
	(0..2*m-1).each{|i|
		v[i, 0] = 1 if edges[i][1] == n
	}
	p (u * exp(mat, z-1) * v)[0, 0] > 0
}