Berilij

Το μικρό πρόβατο, η Be, (συντομογραφία για τη λέξη Berilij) απήχθη από εξωγήινους και έχουν ένα - μάλλον ασυνήθιστο - αίτημα για αυτήν. Θέλουν να την προσλάβουν.

Ακριβώς το Σάββατο ~5~ Νοεμβρίου, οι εξωγήινοι σχεδιάζουν να επισκεφθούν τη Γη με ~n~ διαστημόπλοια και να ανταμείψουν τους καλύτερους διαγωνιζόμενους του COCI (και ίσως να τους προσλάβουν και αυτούς). Τα διαστημόπλοιά τους είναι τέλειοι κύκλοι.

Για λόγους ασφαλείας, επέλεξαν ~m~ ζεύγη διαστημόπλοιων που πρέπει να αγγίζουν εξωτερικά όταν προσγειώνονται. Έχουν ήδη καθορίσει τις συντεταγμένες προσγείωσης του κεντρικού σημείου για κάθε ένα από τα διαστημόπλοια και η αποστολή της Be είναι να προσδιορίσει την ακτίνα καθενός από τα διαστημόπλοια, ώστε να ικανοποιούνται οι συνθήκες.

Τα διαστημόπλοια είναι πολύ ακριβά και το κόστος τους είναι ίσο με την έκτασή τους, έτσι οι εξωγήινοι ζητούν από την Be να καθορίσει τις ακτίνες με το ελάχιστο κόστος των διαστημόπλοιων.

Η προηγμένη τεχνολογία τους, επιτρέπει στα διαστημόπλοια να επικαλύπτονται και, ακόμη πιο ενδιαφέρον, ξέρουν πώς να φτιάξουν ένα διαστημόπλοιο με ακτίνα ίση με ~0~.

Εάν δεν υπάρχει σύνολο ακτίνων που να ικανοποιεί τις προϋποθέσεις, οι εξωγήινοι περιμένουν ότι η Be θα τους ενημερώσει σχετικά. Εάν η Be δεν καταφέρει να καθορίσει τις ακτίνες, θα τον προσλάβουν για μεσημεριανό γεύμα.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς ~n~ και ~m~ ~(1 \le n, m \le 10^5)~, τον αριθμό των διαστημόπλοιων και τον αριθμό των συνθηκών.

Οι ακόλουθες ~n~ γραμμές περιέχουν πραγματικούς αριθμούς ~x_i~ και ~y_i~ ~(-10\,000 \le x_i, y_i \le 10\,000)~, τις συντεταγμένες του κεντρικού σημείου του ~i~-οστού διαστημόπλοιου. Κάθε ένας από τους αριθμούς θα δίνεται με ~10~ δεκαδικά ψηφία.

Οι ακόλουθες ~m~ γραμμές περιέχουν δύο ακέραιους αριθμούς ~a_i~ και ~b_i~ ~(1 \le a_i, b_i \le n,\,a_i \ne b_i)~, που αντιπροσωπεύουν την προϋπόθεση ότι το ~a_i~-οστό και το ~b_i~-οστό διαστημόπλοιο πρέπει να αγγίξουν εξωτερικά μετά την προσγείωση. Για κάθε μη ταξινομημένο ζεύγος ~(a_i, b_i)~ θα υπάρχει το πολύ μία τέτοια συνθήκη.

Έξοδος

Αν δεν υπάρχει λύση, στην πρώτη και μοναδική γραμμή τυπώστε NE. Διαφορετικά, στην πρώτη γραμμή τυπώστε DA, και στην ~i~-οστή από τις ακόλουθες ~n~ γραμμές τυπώστε την ακτίνα του ~i~-οστού διαστημόπλοιου.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	15	Το ~n~ είναι περιττό και καθένα από τα διαστημόπλοια πρέπει να αγγίζει ακριβώς δύο άλλα διαστημόπλοια.
2	25	Υπάρχει τουλάχιστον ένας τρόπος προσδιορισμού των ακτίνων ώστε να ικανοποιούνται οι συνθήκες.
3	30	Για κάθε ζεύγος διαστημόπλοιων ~(a, b)~, υπάρχει το πολύ μια ακολουθία διακριτών διαστημόπλοιων που ξεκινάει στο ~a~ και τελειώνει στο ~b~, και όλα τα παρακείμενα διαστημόπλοια της σειράς είναι απαραίτητα σε επαφή.
4	40	Κανένας επιπλέον περιορισμός.

Η απάντησή σας θα θεωρηθεί σωστή εάν, για κάθε ακτίνα των ~n~ διαστημόπλοιων, το απόλυτο ή σχετικό σφάλμα του δεν υπερβαίνει το ~10^{-4}~. Με άλλα λόγια, εάν η απάντησή σας για το ~i~-οστό διαστημόπλοιο είναι ~r_{si}~ και η σωστή απάντηση ~r_{ci}~, τότε η απάντησή σας θα θεωρηθεί σωστή εάν ~|r_{si} - r_{ci}| \le 10^{-4}~ ή ~|\frac{r_{si} - r_{ci}}{r_{ci}}| \le 10^{-4}~

Παραδείγματα

input

3 3
0.0000000000 0.0000000000
0.0000000000 2.0000000000
2.0000000000 0.0000000000
1 2
2 3
3 1

output

DA
0.585786
1.414214
1.414214

Επεξήγηση του 1ου παραδείγματος:

Αυτή είναι η μόνη λύση που ικανοποιεί όλες τις συνθήκες επαφής. Λάβετε υπόψη ότι η λύση ~(0.585700,\,1.414357, \,1.414357)~ θεωρείται επίσης σωστή, παρόλο που τα διαστημόπλοια ~2~ και ~3~ δεν αγγίζουν, επειδή το απόλυτο σφάλμα δεν υπερβαίνει το ~10^{-4}~.

input

5 4
-0.4585133080 0.2893567973
9.9368007273 7.1806641913
-8.4621834970 -2.8309311865
0.0122121945 -2.8309311865
2.3991780589 -8.8626906628
2 1
3 2
4 3
5 1

output

DA
0.000000
12.472076
8.474396
0.000000
9.587824

input

5 5
0.0000000000 0.0000000000
1.0000000000 2.0000000000
2.0000000000 4.0000000000
3.0000000000 6.0000000000
4.0000000000 8.0000000000
1 2
2 3
3 4
4 5
5 1

output

NE

Επεξήγηση του 3ου παραδείγματος:

Δεν υπάρχει διάταξη των ακτίνων που να ικανοποιεί όλες τις προϋποθέσεις.