Ramen Taste Dilemma

In a distant metropolis, there are \(n\) buildings numbered from \(1\) to \(n\) with building \(1\) being the city centre. The city has \(m\) bidirectional roads; some roads may form a simple cycle (each road is contained in at most one simple cycle). It is known that:

• Every building is reachable from the city centre.
• Each building sells a bowl of ramen, characterized solely by its greasiness which is denoted by a positive integer.

After a long day, rin finds herself at building \(x\). Due to rush‐hour traffic, the following phenomenon occurs:

All unavoidable roads on every simple path from the city centre (building \(1\)) to building \(x\) are blocked. In other words, every road which appears in every simple \(1\)–\(x\) path (i.e. every \(1\)–\(x\) bridge) is blocked. The remaining roads are open.

Using only open roads, rin can travel from building \(x\) to taste the ramen in the accessible buildings (if a building is not reached, its ramen is not counted). For each type of ramen (identified by its greasiness), let the tasting count be the frequency of that ramen type among all accessible buildings. Given a positive integer \(y\), your task is to calculate:

1. The number of ramen types with greasiness \(\le y\) that appear an odd number of times.
2. The number of ramen types with greasiness \(\le y\) that appear an even number of times.

Note: A road is blocked if and only if it is a bridge for the pair \(1\) and \(x\) (i.e. it appears in every simple path from \(1\) to \(x\)).

How to solve: First, identify all bridges in the graph (using, for example, Tarjan's algorithm). Then, using a DFS/BFS starting from building \(1\), record a parent pointer tree. The simple \(1\)–\(x\) path in this tree will include some edges; any edge on this path that is a bridge is an unavoidable road and should be removed from the graph. Finally, from building \(x\) traverse in the modified graph (with blocked roads removed) to collect all reachable buildings, count the frequency of ramen types (by greasiness), and answer the two queries.

inputFormat

The first line contains four integers \(n\), \(m\), \(x\) and \(y\) \((2 \le n \le 10^5,\; 1 \le m \le 2\times10^5,\; 1 \le x \le n,\; 1 \le y \le 10^9)\) representing the number of buildings, the number of roads, the building where rin is located, and the greasiness threshold.

The second line contains \(n\) positive integers, where the \(i\)th integer denotes the greasiness level of the ramen at building \(i\).

Each of the next \(m\) lines contains two integers \(u\) and \(v\) \((1 \le u,v \le n,\; u \neq v)\) representing a bidirectional road connecting buildings \(u\) and \(v\). It is guaranteed that the graph is connected and that each road lies in at most one simple cycle.

outputFormat

Output two integers separated by a space: the first is the number of ramen types with greasiness \(\le y\) that appear an odd number of times in the accessible component (from building \(x\)), and the second is the number that appear an even number of times.

sample

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

1 0