C. Dethrone Antares Now
time limit per test
1.25 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
8 9 3
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 8
8 3
1 5 7
Output
DAN
2
2 3
4 3
8 3
Input
2 1 2
1 2
1 2
Output
DAN'T
Input
8 8 2
1 2
2 3
3 1
1 4
4 6
6 5
7 5
1 8
7 8
Output
DAN
4
5 6 4 1
1 2 3 1