Rick is in love with Unity. But Mr. Meeseeks also love Unity, so Rick and Mr. Meeseeks are "love rivals". 

Unity loves rap, so it decided that they have to compete in a rap game (battle) in order to choose the best. Rick is too nerds, so instead he's gonna make his verse with running his original algorithm on lyrics "Rap God" song.

His algorithm is a little bit complicated. He's made a tree with *n* vertices numbered from 1 to *n* and there's a lowercase english letter written on each edge. He denotes *str*(*a*, *b*) to be the string made by writing characters on edges on the shortest path from *a* to *b* one by one (a string of length equal to distance of *a* to *b*). Note that *str*(*a*, *b*) is reverse of *str*(*b*, *a*) and *str*(*a*, *a*) is empty.

 In order to make the best verse he can, he needs to answer some queries, but he's not a computer scientist and is not able to answer those queries, so he asked you to help him. Each query is characterized by two vertices *x* and *y* (*x* ≠ *y*). Answer to this query is the number of vertices like *z* such that *z* ≠ *x*, *z* ≠ *y* and *str*(*x*, *y*) is lexicographically larger than *str*(*x*, *z*).

String *x*  =  *x*<sub class="lower-index">1</sub>*x*<sub class="lower-index">2</sub>...*x*<sub class="lower-index">|*x*|</sub> is lexicographically larger than string *y*  =  *y*<sub class="lower-index">1</sub>*y*<sub class="lower-index">2</sub>...*y*<sub class="lower-index">|*y*|</sub>, if either |*x*|  &gt;  |*y*| and *x*<sub class="lower-index">1</sub>  =  *y*<sub class="lower-index">1</sub>,  *x*<sub class="lower-index">2</sub>  =  *y*<sub class="lower-index">2</sub>,  ...,  *x*<sub class="lower-index">|*y*|</sub>  =  *y*<sub class="lower-index">|*y*|</sub>, or exists such number *r* (*r*  &lt;  |*x*|,  *r*  &lt;  |*y*|), that *x*<sub class="lower-index">1</sub>  =  *y*<sub class="lower-index">1</sub>,  *x*<sub class="lower-index">2</sub>  =  *y*<sub class="lower-index">2</sub>,  ...,  *x*<sub class="lower-index">*r*</sub>  =  *y*<sub class="lower-index">*r*</sub> and *x*<sub class="lower-index">*r*  +  1</sub>  &gt;  *y*<sub class="lower-index">*r*  +  1</sub>. Characters are compared like their ASCII codes (or alphabetic order).

Help Rick get the girl (or whatever gender Unity has).
The first line of input contain two integers *n* and *q* (2 ≤ *n* ≤ 20000, 1 ≤ *q* ≤ 20000) — number of vertices in tree and number of queries respectively.

The next *n* - 1 lines contain the edges. Each line contains two integers *v* and *u* (endpoints of the edge) followed by an English lowercase letter *c* (1 ≤ *v*, *u* ≤ *n*, *v* ≠ *u*).

The next *q* line contain the queries. Each line contains two integers *x* and *y* (1 ≤ *x*, *y* ≤ *n*, *x* ≠ *y*).
Here's the tree of first sample testcase:

Here's the tree of second sample testcase:

In this test:
 -  *str*(8, 1) = poo -  *str*(8, 2) = poe -  *str*(8, 3) = po -  *str*(8, 4) = pop -  *str*(8, 5) = popd -  *str*(8, 6) = popp -  *str*(8, 7) = p 
So, for the first query, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/9ac3bcb50c63fc450b7ff3ad3f82b1aa9b0ffdb8.png" style="max-width: 100.0%;max-height: 100.0%;"/> and for the third query <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/01f13fd2e1e98dac35dfd28b98a1cdb970305a72.png" style="max-width: 100.0%;max-height: 100.0%;"/> is the answer.
def find(s,h,x,adj_list,cost,count,n):
    if count==n-1:
        return cost
    elif s!=x:
        for i in list(adj_list[x].keys()):
            if i!=h:
                cost[i]=cost[x]+adj_list[x][i]
                find(s,x,i,adj_list,cost,count+1,n)
    else:
        for i in list(adj_list[s].keys()):
            if i!=h:
                cost[i]=adj_list[s][i]
                find(s,s,i,adj_list,cost,count+1,n)
n,q=list(map(int,input().split()))
adj_list,cost={},{}
for i in range(n):
    adj_list[i+1]={}
    cost[i+1]=""
for i in range(n-1):
    line=input().split()
    adj_list[int(line[0])][int(line[1])]=line[2]
    adj_list[int(line[1])][int(line[0])]=line[2]
for i in range(q):
    s,e=list(map(int,input().split()))
    find(s,s,s,adj_list,cost,0,n)
    count=0
    for j in range(n):
        if j+1!=s and j+1!=e:
            lenght=min(len(cost[e]),len(cost[j+1]))
            if cost[e][0:lenght]==cost[j+1][0:lenght] and len(cost[e])>lenght:
                count+=1
            else:
                for z in range(min(len(cost[e]),len(cost[j+1]))):
                    if cost[e][z]>cost[j+1][z]:
                        count+=1
                        break
    print(count)
