Problem I: Red-Blue Tree

Given a rooted tree T and a set S of pairs of vertices from T, we say that T is a red-blue tree on S if it is possible to colour every vertex in the tree with either red or blue such that the following holds:

For each pair of vertices (a,b) in S, consider the unique path in T connecting a to b. Any two vertices on this path that share a common parent in T must be coloured with different colours.

Given a rooted tree T, a set of vertex pairs S, and the fact that T is a red-blue tree on S, you are to find the maximum number of pairs from S that can be simultaneously connected in T using each tree edge at most once.

Input Format

Each test case starts with three integers 1 ≤ n ≤ 100, 0 ≤ k ≤ 3000 and 1 ≤ r ≤ n which are the number of vertices, number of pairs and index of the root, respectively. Next n -1 lines contain two integers between 1 and n describing two endpoints of an edge. Next k lines contain two integers between 1 and n giving a pair of vertices. Input is terminated with a line consisting of n = k = r = 0. You are guaranteed each input graph is a connected tree rooted at the given r and is a red-blue tree on the given pairs.

Output Format

There is a line of output for each test case containing the maximum number of pairs from the given list that can be simultaneously connected using each tree edge at most once.

Sample Input

16 12 1
1 2
1 3
1 4
1 5
1 6
1 7
2 8
2 9
2 10
3 11
3 12
3 13
4 14
4 15
4 16
8 5
5 9
6 8
6 12
7 11
7 15
8 10
9 10
11 13
12 13
14 16
15 16
0 0 0

Sample Output

6