n,m,t=gets.split.map(&:to_i)
l=[]
n.times do
  l << []
end
m.times do
  a,b=gets.split.map(&:to_i)
  l[a] << b
end
r=Hash.new(nil)
s=[0]
i=0
r[s.dup]=i
while s!=[]&&i<t
  z=[]
  s.each do |ss|
    l[ss].each do |lss|
      z << lss
    end
  end
  s=z.dup.uniq
  i+=1
  sd=s.sort.dup
  if r[sd]
    i=t-(t-i)%(i-r[sd])
    r=Hash.new(nil)
  else
    r[sd]=i
  end
end
puts s.size