Lower Carniolan

Osnovne informacije

Omejitve
  • Čas: 2 s
  • Spomin: 128 MB
Avtor:
  • Vid Kocijan
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Task description for ordinary mortals

Polde the Lower Carniolan managed to catch a golden fish which can fulfill any wish of his. He had always wished that he could walk from pub to pub for all eternity. The golden fish made his wish come true. Soon after that Polde rethought his decision, but it was already too late. He is now immortal and doomed to spend the rest of eternity walking from pub to pub. He can not take a rest in any of the pubs. He can only grab his drink and continue his walk. Polde's village has n buildings labelled by integers from 1 to n. Those building are connected by m one-directional roads. There are d pubs in his village and they are located in buildings with labels f_1, \ldots, f_d. Suppose that Polde starts his walk at building q_0. Is it possible for him to walk from pub to pub forever using only the roads? More formally, Polde's walk along the roads should be infinite and it has to contain infinitely many visits to one or more buildings in which pubs are located. It doesn't matter which pubs he visits, or what number of other buildings he passes by.

Task description for theoretical computer scientists

We are given a non-deterministic Büchi automaton A=(Q=\{1,\ldots,n\},\Sigma=\{0\},\Delta,I=\{q_0\},F). Does it hold that L(A)\neq \emptyset?

The first line contains numbers n=|Q|, m=|\Delta|, d=|F| and q_0. The second line contains space-separated elements f_1, \ldots, f_d \in F. The following m lines contain elements of the relation \Delta \subseteq Q \times Q. Your program should output DA if L(A)\neq \emptyset, and NE otherwise.

Input

The first line contains space-separated integers n, m, d and q_0.

The second line contains d space-separated integers f_1, \ldots, f_d, i.e. the list of pub locations.

Each of the remaining m lines contains two (not necessarily distinct) integers b_i and c_i. There is a one-directional road going from building b_i to building c_i.

Input limits

  • 1 \leq n,m,d \leq 10^5

Output

Output DA if Polde can walk from pub to pub for all eternity, otherwise output NE.

Examples

Input

3 2 1 1
3
1 2
2 3

Output

NE

Input

4 5 3 1
3 4 1
1 2
2 3
3 2
2 4
4 2

Output

DA

Input

3 3 1 1
3
1 2
2 3
3 3

Output

DA

Comment

In the first example, Polde can arrive to the pub in building 3, but he can not continue his walk from that point.

In the second example, Polde can reach the pub in building 3 and he can spend the rest of eternity going from the pub in building 3 to the pub in building 4 (and back).

In the third example, Polde can walk from the pub in building 3 back to the same pub.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task