One day Polycarp published a funny picture in a social network making a poll about the color of his handle. Many of his friends started reposting Polycarp's joke to their news feed. Some of them reposted the reposts and so on.

These events are given as a sequence of strings "name1 reposted name2", where name1 is the name of the person who reposted the joke, and name2 is the name of the person from whose news feed the joke was reposted. It is guaranteed that for each string "name1 reposted name2" user "name1" didn't have the joke in his feed yet, and "name2" already had it in his feed by the moment of repost. Polycarp was registered as "Polycarp" and initially the joke was only in his feed.

Polycarp measures the popularity of the joke as the length of the largest repost chain. Print the popularity of Polycarp's joke.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 200) — the number of reposts. Next follow the reposts in the order they were made. Each of them is written on a single line and looks as "name1 reposted name2". All the names in the input consist of lowercase or uppercase English letters and/or digits and have lengths from 2 to 24 characters, inclusive.

We know that the user names are case-insensitive, that is, two names that only differ in the letter case correspond to the same social network user.


-----Output-----

Print a single integer — the maximum length of a repost chain.


-----Examples-----
Input
5
tourist reposted Polycarp
Petr reposted Tourist
WJMZBMR reposted Petr
sdya reposted wjmzbmr
vepifanov reposted sdya

Output
6

Input
6
Mike reposted Polycarp
Max reposted Polycarp
EveryOne reposted Polycarp
111 reposted Polycarp
VkCup reposted Polycarp
Codeforces reposted Polycarp

Output
2

Input
1
SoMeStRaNgEgUe reposted PoLyCaRp

Output
2

Difficulty: interview

Starter code:

Solutions:
import sys

def main():
    mx = 1
    n = int(input())
    D = {}
    D["polycarp"] = 1
    for i in range(n):
        s, r, t = input().split()
        s = s.lower()
        t = t.lower()
        D[s] = D[t] + 1
        mx = max(mx, D[s])
    print(mx)

main()

n = int(input())
m = {'polycarp' : 0}
for i in range(n):
    s, r, t = input().lower().split()
    m[s] = m[t] + 1
mx = 0
for y in list(m.values()):
    mx = max(mx, y)
print(mx + 1)


#!/usr/bin/env python3.4

n = int(input())
ans = {'polycarp':1}
for i in range(n):
    repost, _, reposted = input().lower().split()
    ans[repost] = ans[reposted] + 1
print(max(ans.values()))


sa = []
a = int(input())
for i in range(a):
    x = list(map(str, input().split(' reposted ')))
    sa.append([x[0].lower(), x[1].lower()])

l = {"polycarp":1}

d = {}
for i in sa:
    d[i[0]] = i[1]
    
for i in sa:
    if i[0] not in l:
        l[i[0]] = l[i[1]] + 1
        
print(max([l[t] for t in l]))


n = int(input())
d = {'polycarp': 1}
m = 1
for i in range(n):
    s = input().lower().split()
    d[s[0]] = d[s[2]] + 1
    if d[s[0]] > m:
        m = d[s[0]]
print(m)

n, qwe = int(input()), {'polycarp' : 1}
for _ in range(n):
	t = input().split(' reposted ')
	qwe[t[0].lower()] = qwe[t[1].lower()] + 1
print(max(qwe.values()))

m = dict()
n = int(input().strip())
m['polycarp'] = 0
for i in range(n):
    n1, n2 = input().rstrip().lower().split(' reposted ', 1)
    m[n1] = m[n2] + 1
print(max(m.values()) + 1)




def reg(s):
    s1 = ''
    for i in s:
        if ord(i) >= ord('A') and ord(i) <= ord('Z'):
            s1 += chr(ord(i) - ord('A') + ord('a'))
        else:
            s1 += i
    return s1

s = set()
a = int(input())
d = dict()
t = 0
repeat = []
for i in range(a):
    x, y, z = map(str, input().split())
    if reg(x) not in d:
        d[reg(x)] = t
        t += 1
    if reg(z) not in d:
        d[reg(z)] = t
        t += 1
    s.add(reg(x))
    s.add(reg(z))
    repeat.append((d[reg(x)], d[reg(z)]))
l = [[] for i in range(len(s) + 1)]
for i in repeat:
    l[i[0]].append(i[1])
    l[i[1]].append(i[0])
n = len(s)
f = [-1] * (n + 1)
q = [0] * (n + 1)
f[d['polycarp']] = 0
q[0] = d['polycarp']
h = 0
t = 1
while h < t:
    i = q[h]
    h += 1
    for j in l[i]:
        if f[j] == -1:
            f[j] = f[i] + 1
            q[t] = j
            t += 1
print(max(f) + 1)

#!/bin/env python3

from sys import stdin
import re

guys = { 'polycarp': 1 }

res = 1
stdin.readline()
for line in stdin:
    try:
        to, _, fr = [s.strip().lower() for s in line.lstrip().split(' ', 2)]
    except:
        continue
    guys[to] = max(guys[fr] + 1, guys.get(to, 0))
    res = max(guys[to], res)

print (res)


count = int(input())
tree = {'polycarp' : 1}
max = 1;
for i in range(0, count):
	try:
		rel = input().lower().split(' ')
		if not rel[1] == 'reposted': 
			continue
		tree[rel[0]] = tree[rel[2]] + 1
		if tree[rel[0]] > max: 
			max = tree[rel[0]]
	except BaseException:
		continue
print(max)

N = input()
N = int(N)
res = 0
graph = [["polycarp"]]
for i in range(N):
	data = input().split(' ')
	reposter = data[0].lower()
	reposted = data[2].lower()
	length = len(graph)
	for i in range(length):
		if reposted in graph[i]:
			if i < length-1:
				graph[i+1].append(reposter)
			else:
				graph.append([reposter])
print(len(graph))

import sys

def add_user(d, u):
    if u in d:
        return d[u]
    else:
        d[u] = len(d)
        return d[u]

n = int(input())
who = [[] for i in range(n+1)]
users = {}
answer_id = -1
for i in range(n):
    str = input()
    parts = str.split(' ')
    name_one = parts[0].lower()
    name_two = parts[2].lower()
    user_one = add_user(users, name_one)
    user_two = add_user(users, name_two)
    who[user_two].append(user_one);
    if name_two == 'polycarp':
        answer_id = user_two

def dfs(u):
    res = 1
    for v in who[u]:
        res = max(res, dfs(v) + 1);

    return res

print((dfs(answer_id)));



result = []
pol = 'polycarp'
for i in range(int(input())):
    point = False
    new_person, _, was = [x.lower() for x in input().split()]
    if was == pol: result.append([pol, new_person])
    elif was in [x[-1] for x in result]:
        for line in result:
            if line[-1] == was:
                line.append(new_person)
                break
    else:
        for line in result:
            for name in line[1:-1]:
                if name == was:
                    i = line.index(name)
                    new_person_line = line[:i+1]
                    new_person_line.append(new_person)
                    result.append(new_person_line)
                    point = True
                    break
            if point: break
                    
m = max(len(line) for line in result)
print(m)


def lower(a):
    if 'A' <= a <= "Z":
        return chr(ord(a) + 32)
    else:
        return a


def ToLower(a):
    a = list(a)
    for i in range(len(a)):
        a[i] = lower(a[i])
    return ''.join(a)

def main():
    n = int(input())
    people = ['polycarp']
    res = [1] * (n + 1)
    for i in range(1, n + 1):
        a, b, c = map(ToLower, input().split())
        res[i] = res[people.index(c)] + 1
        people.append(a)
    print(max(res))
main()

n = int(input())
d = {}
d["polycarp"] = 1
ans = 1

for i in range(n):
    s = input()
    a = s.split()
    a[0] = a[0].lower()
    a[2] = a[2].lower()
    d[a[0]] = d[a[2]] + 1
    ans = max(ans, d[a[0]])

print(ans)


deep = dict()
n = int(input())
adj_dict = dict()
for i in range(n):
    line = [s.lower() for s in input().split()]
    name1 = line[0]
    name2 = line[2]
    if name2 not in list(adj_dict.keys()):
        adj_dict[name2] = list()
        adj_dict[name2].append(name1)
    else:
        adj_dict[name2].append(name1)
    deep[name1] = 0
    deep[name2] = 0
queue = list()
queue.append('polycarp')
while queue:
    current = queue[0]
    queue = queue[1:]
    if current not in adj_dict:
        continue
    for nei in adj_dict[current]:
        deep[nei] = deep[current] + 1
        queue.append(nei)

print(max(deep.values()) + 1)


n = int(input())
c = {}
c['polycarp'] = []
for i in range(n):
	s = input().split(' reposted ')
	s[0] = s[0].lower()
	s[1] = s[1].lower()
	if s[0] not in c:
		c[s[0]] = []
	c[s[1]] += [c[s[0]]]
answ = str(c['polycarp'])
count = 0
m = 0
for i in answ:
	if i == '[':
		count += 1
		if count > m:
			m = count
	elif i == ']':
		count -= 1
print(m)

def nafig(s):
    for i in range(len(s)):
        x = ord(s[i])
        if (x <= 90) and (x >= 65):
            x += 32
            s = s[:i] + chr(x) + s[i + 1:]
    return s


n = int(input())
dic = dict()
dic['polycarp'] = 1
maxim = 1
for i in range(n):
    st = list(map(str, input().split()))
    st[0] = nafig(st[0])
    st[2] = nafig(st[2])
    dic[st[0]] = dic[st[2]] + 1
    if dic[st[0]] > maxim:
        maxim = dic[st[0]]
print(maxim)




def r(d,key):
    if key in d:
        s=0
        for i in d[key]:
            m=r(d,i)
            if m>s: s=m
        return s+1
    else: return 1

def size(d):
    s=0
    for i in d:
        m=r(d,i)
        if m>s: s=m
    return s

n=int(input())
a=[input().lower().split() for i in range(n)]
d={}
for i in a:
    d[i[2]]=[]
for i in a:
    d[i[2]].append(i[0])
s=size(d)
print(s)



def main():
	N = int(input())
	users = {}
	users['polycarp'] = 1

	for x in range(N):
		msg = input().split()
		user1, user2 = msg[0].lower(), msg[2].lower()
		users[user1] = users[user2] + 1

	print(max(users.values()))

main()


__author__ = 'ruckus'

def haveLast(Chains, Name):
    for i in range(len(Chains)):
        if Chains[i][len(Chains[i])-1] == Name:
            return i
    return -1

RepostNum = int(input())

Reposts = []

for i in range(RepostNum):
    Reposts.append(input().split())
    Reposts[i][0] = Reposts[i][0].upper()
    Reposts[i][2] = Reposts[i][2].upper()

MaxRepostLen = 1

Chains = []

for i in range(RepostNum):
    if Reposts[i][2] == 'Polycarp'.upper():
        Chains.append(['Polycarp'.upper(), Reposts[i][0]])
    else:
        num = haveLast(Chains, Reposts[i][2])
        if num >= 0:
            Chains[num].append(Reposts[i][0])
        else:
            for j in range(len(Chains)):
                if Reposts[i][2] in Chains[j]:
                    Chains.append(Chains[j][:Chains[j].index(Reposts[i][2])+1])
                    Chains[len(Chains)-1].append(Reposts[i][0])

for Chain in Chains:
    if len(Chain) > MaxRepostLen:
        MaxRepostLen = len(Chain)

print(MaxRepostLen)

n = int(input())
reposted_list = {"polycarp": 1}

for i in range(n):
    reposter, r, author = input().split(" ")
    reposter, author = reposter.lower(), author.lower()
    reposted_list[reposter] = reposted_list[author] + 1

print(reposted_list[max(reposted_list, key=reposted_list.get)])

def length(arr, nowman):
    l = 1
    if nowman != 'polycarp':
        l += length(arr, arr[nowman])
    return l

rarr = {}
for i in range(int(input())):
    r = input().lower().split()
    rarr[r[0]] = r[2]

maxl = 1
for key, value in list(rarr.items()):
    l = length(rarr, rarr[key])+1
    if maxl < l:
        maxl = l

print(maxl)


import sys

__author__ = 'zumzoom'

n = int(sys.stdin.readline())
edges = sys.stdin.readlines()
d = dict()
d['polycarp'] = 1
for edge in edges[:n]:
    a = edge.lower().split()
    d[a[0]] = d[a[2]] + 1

print(max(d.values()))



#!/usr/bin/env python3
# coding: utf-8

n = int(input())

repost_level = {"polycarp": 1}

for i in range(n):
    name1, _, name2 = input().split()
    repost_level[name1.lower()] = repost_level[name2.lower()] + 1


print(max(repost_level.values()))