Trading Union Departures

A long time ago in a galaxy far, far away, a large interstellar trading union joined countries from all across the galaxy. Recently one of them decided to leave. Other countries are now considering the same, because membership stops paying off once their main trading partners are gone.

You are a citizen of country $X$ and you want to know whether your country stays in the union. You have written down every pair of countries that trade with each other. If at least half of the original trading partners of a country $Y$ leave the union, $Y$ leaves soon after. Country $L$ is the only country that leaves on its own; every other departure follows from that rule.

The partner count of a country is fixed by the list in the input and never shrinks when a partner leaves. Decide whether country $X$ leaves the union once no further departure happens.

The first line contains four space separated integers $C$, $P$, $X$ and $L$. $C$ is the number of countries ($2 \le C \le 200000$), $P$ is the number of trading partnerships ($1 \le P \le 300000$), $X$ is the number of your home country ($1 \le X \le C$), and $L$ is the number of the first country to leave ($1 \le L \le C$).

Each of the next $P$ lines contains two space separated integers $A_i$ and $B_i$ with $1 \le A_i < B_i \le C$. Such a line means countries $A_i$ and $B_i$ are trading partners. No pair of countries is listed more than once.

Initially every country has at least one trading partner in the union.

Print one line containing leave if country $X$ leaves the union, or stay if it remains.