Brexit

A long time ago in a galaxy far, far away, there was a large interstellar trading union, consisting of many countries from all across the galaxy. Recently, one of the countries decided to leave the union. As a result, other countries are thinking about leaving too, as their participation in the union is no longer beneficial when their main trading partners are gone.

You are a concerned citizen of country $X$, and you want to find out whether your country will remain in the union or not. You have crafted a list of all pairs of countries that are trading partners of one another. If at least half of the trading partners of any given country $Y$ leave the union, country $Y$ will soon follow. Given this information, you now intend to determine whether your home country will leave the union.

The input starts with one line containing four space separated integers $C$, $P$, $X$, and $L$. These denote the total number of countries ($2 \leq C \leq 200\, 000$), the number of trading partnerships ($1 \leq P \leq 300\, 000$), the number of your home country ($1 \leq X \leq C$) and finally the number of the first country to leave, setting in motion a chain reaction with potentially disastrous consequences ($1 \leq L \leq C$).

This is followed by $P$ lines, each containing two space separated integers $A_ i$ and $B_ i$ satisfying $1 \leq A_ i < B_ i \leq C$. Such a line denotes a trade partnership between countries $A_ i$ and $B_ i$. No pair of countries is listed more than once.

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

For each test case, output one line containing either
“`leave`” or “`stay`”, denoting whether you home country leaves
or stays in the union.

Sample Input 1 | Sample Output 1 |
---|---|

4 3 4 1 2 3 2 4 1 2 |
stay |

Sample Input 2 | Sample Output 2 |
---|---|

5 5 1 1 3 4 1 2 2 3 1 3 2 5 |
leave |

Sample Input 3 | Sample Output 3 |
---|---|

4 5 3 1 1 2 1 3 2 3 2 4 3 4 |
stay |

Sample Input 4 | Sample Output 4 |
---|---|

10 14 1 10 1 2 1 3 1 4 2 5 3 5 4 5 5 6 5 7 5 8 5 9 6 10 7 10 8 10 9 10 |
leave |