CFT15

#### Start

2018-05-21 00:00 UTC

## CFT15

#### End

2018-05-22 00:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -306 days 1:06:44

24:00:00

0:00:00

# Problem DBrexit

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.

## Input

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.

## Output

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