Miami CSE Open

#### Start

2017-10-05 00:20 CEST

## Miami CSE Open

#### End

2017-10-05 03:20 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -381 days 8:04:10

3:00:00

0:00:00

# Problem FBrexit

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