Background

Why is it like this? You pull me and say you are hesitating.
Why is it like this? The rain has not stopped, yet you open an umbrella and want to leave.
I am already used to not stopping you. After a while, you will come back.
The love in my memory seems unable to withstand time.
—— “Peninsular Iron Box” (link).

Problem Description

Brief statement

You are given an undirected graph with $n$ vertices and $m$ edges. It may contain multiple edges and self-loops, and it may be disconnected.

Initially, each vertex has a vertex weight, which is a random positive real number. Now you need to redistribute the vertex weights so that:

1. For any two adjacent vertices, the ratio of the larger weight to the smaller weight does not exceed $x$.

2. The total sum of vertex weights remains unchanged.

3. The weight of each vertex is not less than $\dfrac{p}{q}$ of its initial weight.

Find the minimum $x \ge 1$ such that, for the given graph, no matter what the initial vertex weights are, there always exists a redistribution that satisfies all requirements above.

Original statement

A god created a world inside a peninsular iron box.

This world consists of $n$ regions and $m$ passages between regions. Each passage connects two regions. At creation, each region has a certain air pressure, and the pressure is a positive number.

Since the world has just been created and is rather chaotic, there may be multiple passages connecting the same two regions; a region may also have a passage that connects to itself; and two regions may be unable to reach each other through any number of passages.

If the ratio of the air pressures of the two regions connected by a passage (larger divided by smaller, same below) is too large, strong winds will form in the passage, making inter-region travel very dangerous. Therefore, the god decides to adjust the air pressure of each region so that, for every passage, the ratio of the pressures at its two ends does not exceed a safe ratio $x$. Clearly, $x \ge 1$.

Since breaking various conservation laws would be troublesome, the god wants the sum of air pressures over all regions to remain the same before and after the adjustment.

Since creatures in this world cannot survive under overly low pressure but adapt well to high pressure, the adjusted pressure of each region must not be lower than $\dfrac{p}{q}$ of its initial value.

Because the initial pressures are random and not controlled by the god, the god wants the safe ratio $x$ to be such that, no matter what the initial pressures are, there always exists a suitable way to adjust the pressures.

Since wider passages make travel more comfortable, but also require a smaller safe ratio $x$, the god wants to find the minimum safe ratio $x$ that meets the requirements.

As the god is busy dealing with creation affairs, you are appointed to solve this problem.

Input Format

The first line contains four positive integers $n, m, p, q$, with the meanings as described above.

The next $m$ lines each contain two positive integers $u, v$, indicating that a passage connects regions $u$ and $v$.

Output Format

Output a real number representing the minimum value of $x$, rounded to $7$ digits after the decimal point.

This problem uses a Special Judge. Your answer is accepted if the difference between your answer and the reference answer does not exceed $10^{-4}$ times the reference answer.

3 2 1 2
1 2
2 3

2.0000000

10 20 13 37
1 2
1 3
1 5
2 4
2 5
2 6
3 4
3 5
3 7
3 9
3 10
4 6
4 7
4 8
5 7
5 9
7 8
7 9
7 10
9 10

3.6903390

Hint

Constraints

For $10\%$ of the testdata, $np \le q$.

For another $20\%$ of the testdata, there is one region that has a passage connecting it to every other region.

For another $30\%$ of the testdata, the passages form a tree.

For $100\%$ of the testdata, $1 \le u, v \le n \le 10^3$, $1 \le m \le 3 \times 10^4$, $1 \le p < q \le 10^7$.

Translated by ChatGPT 5