Maximum Unique Statues

Bob wants to photograph as many unique statues as possible in a network of walkways. In this problem, each statue is placed on a specific walkway (edge) called a statue path. Bob starts his journey at a given intersection S and must return to the same intersection after his walk. Along the way, whenever he travels an edge that contains a statue, he can capture its photo (each statue is counted only once, even if the same edge is used multiple times). The objective is to determine the maximum number of unique statues Bob can photograph on any route beginning and ending at S.

The network is represented as an undirected graph. Each edge between two intersections might be a walkway and a potential statue path.

The problem can be formalized as follows: Given integers \(N\) (number of intersections), \(M\) (number of walkways), \(k\) (number of statue paths provided), and the starting intersection \(S\), along with a list of \(P\) statue paths and a list of \(W\) walkways, compute the maximum number of unique statue edges reachable from \(S\). If an edge is a statue path, it is counted once regardless of how many times it might be traversed.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains four space-separated integers: \(N\), \(M\), \(k\), and \(S\).
2. The second line contains an integer \(P\), the number of statue paths.
3. Each of the next \(P\) lines contains two integers \(u\) and \(v\), indicating that there is a statue on the edge connecting intersections \(u\) and \(v\).
4. The next line contains an integer \(W\), the number of walkways.
5. Each of the next \(W\) lines contains two integers \(u\) and \(v\), representing a walkway connecting intersections \(u\) and \(v\).

outputFormat

The output is written to stdout and consists of a single integer: the maximum number of unique statues Bob can photograph on a route that starts and ends at the intersection \(S\).

5 5 2 1
2
1 2
2 3
5
1 2
2 3
3 4
4 5
5 1

2