Rebellious Fingers hackers got a file that showed the bavs hierarchy that connected two certain companies. So they decided to monitor everyone who linked these two companies. Given a person's hierarchy related to these companies and the IDs of an employee of each company, they want to know how many people at least need to be monitored so that all connections between the companies are monitored. A person connects two companies if he/she is boss (directly or indirectly) of members of both companies simultaneously.

The input begins with a line with two integers N and M, splited by one space. The next N lines are composed of two strings A and B, showing that A is a direct boss of B. For each of the next M lines, two strings are given indicating the aforementioned employees. For each of these M lines, there must be an output line, indicating at least how many people must be monitored in this situation.

Example:

input:

5 2

5 1

1 3

5 6

6 4

4 2

2 3

3 2

output:

1

1

Server: openssl s_client -connect programming.pwn2.win:9003

Connection template:

[Link](https://cloud.ufscar.br:8080/v1/AUTH _c93b694078064b4f81afd2266a502511/static.pwn2win.party/the-bavarian-hier archy-template_7684169bed405726993790ac237e21e67d71c532fc1c81005332f605b 2de4548.tar.gz)

[Mirror](https://static.pwn2win.party/the-bavarian-hier archy-template_7684169bed405726993790ac237e21e67d71c532fc1c81005332f605b 2de4548.tar.gz)